On triangulation axes of polygons. (English) Zbl 1358.68298
Summary: 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(n\log n)\) overall time, to an axis competitive to ‘high quality axes’ requiring \(\Theta(n^3)\) time for optimization via dynamic programming.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
computational geometry; polygon; medial axis; anisotropic distance; triangulation; edge flippingReferences:
| [1] | Ai, T.; van Oosterom, P., GAP-tree extensions based on skeletons, (Proc. 10th Int. Symposium on Advances in Spatial Data Handling (2002), Springer-Verlag), 501-513 |
| [2] | Aichholzer, O.; Aigner, W.; Aurenhammer, F.; Hackl, T.; Jüttler, B.; Rabl, M., Medial axis computation for planar free-form shapes, Comput. Aided Des., 41, 339-349 (2009) |
| [3] | Aichholzer, O.; Alberts, D.; Aurenhammer, F.; Gärtner, B., A novel type of skeleton for polygons, J. Univers. Comput. Sci., 1, 752-761 (1995) · Zbl 0943.68171 |
| [4] | Aigner, W.; Aurenhammer, F.; Jüttler, B., On triangulation axes of polygons, (Proc. 28th European Workshop on Computational Geometry (2012)), 125-128 |
| [5] | Amenta, N.; Bern, M., Surface reconstruction by Voronoi filtering, Discrete Comput. Geom., 22, 481-504 (1999) · Zbl 0939.68138 |
| [6] | Attali, D.; Boissonnat, J.-D.; Edelsbrunner, H., Stability and computation of medial axes—a state-of-the-art report, (Müller, T.; Hamann, B.; Russell, B., Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, Springer Series on Mathematics and Visualization (2008)), 109-125 · Zbl 1192.68555 |
| [7] | Aurenhammer, F., Weighted skeletons and fixed-share decomposition, Comput. Geom., 40, 93-101 (2007) · Zbl 1138.65018 |
| [8] | Aurenhammer, F.; Klein, R.; Lee, D. T., Voronoi Diagrams and Delaunay Triangulations (2013), World Scientific Publishing Company: World Scientific Publishing Company Singapore · Zbl 1295.52001 |
| [9] | Bajaj, C., The algebraic degree of geometric optimization problems, Discrete Comput. Geom., 3, 177-191 (1988) · Zbl 0647.90087 |
| [10] | Chew, L. P., Constrained Delaunay triangulations, Algorithmica, 4, 97-108 (1989) · Zbl 0664.68042 |
| [11] | Chew, L. P.; Drysdale, R. L.S., Voronoi diagrams based on convex distance functions, (Proc. 1st Ann. ACM Symposium on Computational Geometry (1985)), 235-244 |
| [12] | De Loera, J.; Rambau, J.; Santos, F., Triangulations, Algorithms and Computation in Mathematics, vol. 25 (2010), Springer-Verlag · Zbl 1207.52002 |
| [13] | Klincsek, G. T., Minimal triangulations of polygonal domains, Ann. Discrete Math., 9, 121-123 (1980) · Zbl 0452.05002 |
| [14] | Labelle, F.; Shewchuk, J. R., Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation, (Proc. 19th Ann. ACM Symposium on Computational Geometry (2003)), 191-200 · Zbl 1375.68154 |
| [15] | Lee, D. T.; Lin, A. K., Generalized Delaunay triangulation for planar graphs, Discrete Comput. Geom., 1, 201-217 (1986) · Zbl 0596.52007 |
| [16] | Siddiqi, K.; Pizer, S. M., Medial Representations: Mathematics, Algorithms, and Applications, Springer Series on Computational Imaging and Vision, vol. 37 (2008) · Zbl 1151.00014 |
| [17] | Tanase, M.; Veltkamp, R. C., A straight skeleton approximating the medial axis, (Proc. 12th Ann. European Symposium on Algorithms. Proc. 12th Ann. European Symposium on Algorithms, Springer Lecture Notes in Computer Science, vol. 3221 (2004)), 809-821 · Zbl 1111.68729 |
| [18] | Wang, T., Extraction of optimal skeleton of polygon based on hierarchical analysis, (Zhang, J.; etal., Int. Archives of Photogrammetry, Remote Sensing, and Spatial Information Sciences, vol. 28-7/C4 (2009)), 272-276 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
