A Novel Type of Skeleton for Polygons

Oswin Aichholzer (Institute for Theoretical Computer Science, Graz University of Technology, Austria)

Franz Aurenhammer (Institute for Theoretical Computer Science, Graz University of Technology, Austria)

David Alberts (Institut für Informatik, Freie Universität Berlin, Germany)

Bernd Gärtner (Institut für Informatik, Freie Universität Berlin, Germany)

Abstract: A new internal structure for simple polygons, the straight skeleton, is introduced and discussed. It is composed of pieces of angular bisectores which partition the interior of a given n-gon P in a tree-like fashion into n monotone polygons. Its straight-line structure and its lower combinatorial complexity may make the straight skeleton preferable to the widely used medial axis of a polygon. As a seemingly unrelated application, the straight skeleton provides a canonical way of constructing a polygonal roof above a general layout of ground walls.

Keywords: Simple polygon, angular bisectors, internal skeleton, roof construction