Paper Info
Title
On triangulation axes of polygons.
Abstract
We propose the triangulation axis as an alternative skeletal structure for a simple polygon P. This axis is a straight-line tree that can be interpreted as an anisotropic medial axis of P, where inscribed disks are line segments or triangles. The underlying triangulation that specifies the anisotropy can be varied, to adapt the axis so as to reflect predominant geometrical and topological features of P. Triangulation axes typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of P. Still, they retain important properties, as for example the reconstructability of P from its skeleton. Triangulation axes can be computed from their defining triangulations in O(n) time. We investigate the effect of using several optimal triangulations for P. In particular, careful edge flipping in the constrained Delaunay triangulation leads, in O(nlog⁡n) overall time, to an axis competitive to ‘high quality axes’ requiring Θ(n3) time for optimization via dynamic programming.
Year
DOI
Venue
2015
10.1016/j.ipl.2014.08.006
Information Processing Letters
Keywords
Field
DocType
Computational geometry,Polygon,Medial axis,Anisotropic distance,Triangulation,Edge flipping
Combinatorics,Straight skeleton,Medial axis,Triangulation (social science),Geometry,Constrained Delaunay triangulation,Mathematics,Polygon triangulation,Point set triangulation,Pitteway triangulation,Delaunay triangulation
Journal
Volume
Issue
ISSN
115
1
0020-0190
Citations 
PageRank 
References 
0
0.34
10
Authors
3
Name
Order
Citations
PageRank
Wolfgang Aigner1252.43
Franz Aurenhammer22060202.90
Bert Jüttler3114896.12