On triangulation axes of polygons

W. Aigner, F. Aurenhammer, and B. Jüttler

Abstract:

We define the triangulation axis of a simple polygon $P$ as an anisotropic medial axis of $P$ whose `unit 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 are piecewise linear skeletons, and typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of $P$ (between $n-2$ and $2n-6$ edges, compared to $2n-3$). Still, they retain important properties, as for example the reconstructability of $P$ from its skeleton. Triangulation axes can be easily 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(n \log n)$ overall time, to an axis competitive to high quality axes requiring $O(n^3)$ time for optimization via dynamic programming.



Reference: W. Aigner, F. Aurenhammer, and B. Jüttler. On triangulation axes of polygons. Information Processing Letters, 115:45-51, 2015.