Abstract
We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
[AART] O. Aichholzer, F. Aurenhammer, G. Rote, and M. Taschwer, Triangulations intersect nicely,Proc. 11th Ann. Symp. on Computational Geometry, Vancouver, British Columbia, June 1995, pp. 220–229.
[AARX] O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu, New greedy triangulation algorithms, in preparation.
[B1] B. Bollobás,Graph Theory. An Introductory Course, Springer-Verlag, Berlin, 1979.
[B2] R. A. Brualdi, Comments on bases in dependence structures,Bull. Austral. Math. Soc. 1 (1969), 161–167.
[B3] T. H. Brylawski, Some properties of basic families of subsets,Discrete Math. 6 (1973), 333–341.
[CX1] S.-W. Cheng and Y.-F. Xu, Constrained independence system and triangulations of planar point sets, in: D.-Z. Du and Ming Li, (eds.),Computing and Combinatorics, Proc. First Ann. Internat. Conf., COCOON'95, Xi'an, China, August 1995. Lecture Notes in Computer Science, Vol. 959, Springer-Verlag, Berlin, 1995, pp. 41–50.
[CX2] S.-W. Cheng and Y.-F. Xu, Approaching the largest β-skeleton within a minimum-weight triangulation,Proc. 12th Ann. Symp. on Computational Geometry, Philadelphia, PA, 1996, pp. 196–203.
[DJ] G. Das and D. Joseph, Which triangulations approximate the complete graph,Proc. Internat. Symp. on Optimal Algorithms, Lecture Notes in Computer Science, Vol. 401, Springer-Verlag, Berlin, 1989, pp. 168–192.
[DDMW] M. Dickerson, R. L. Drysdale, S. McElfresh, and E. Welzl, Fast greedy triangulation algorithms,Proc. 10th Ann. Symp. on Computational Geometry, 1994, pp. 211–220.
[DDS] M. Dickerson, R. L. Drysdale, and J.-R. Sack, Simple algorithms for enumerating interpoint distances and findingk nearest neighbors,Internat. J. Comput. Geom. Appl. 3 (1992), 221–239.
[DM] M. T. Dickerson and M. H. Montague, A. (usually?) connected subgraph of the minimum weight triangulation,Proc. 12th Ann. Symp. on Computational Geometry, Philadelphia, PA, 1996, pp. 204–213.
[DRA] R. L. Drysdale, G. Rote, and O. Aichholzer, A simple linear time greedy triangulation algorithm for uniformly distributed points, Report IIG-408, Institutes for Information Processing, Technische Universität Graz, February 1995, 16 pages.
[GJ] M. Garey and D. Johnson,Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[G] S. Goldman, A space efficient greedy triangulation algorithm,Inform. Process. Lett. 31 (1989), 191–196.
[HK] J. E. Hopcroft and R. Karp, Ann 5/2 algorithm for maximum matchings in bipartite graphs,SIAM J. Comput. 2 (1973), 225–231.
[HNU] F. Hurtado, M. Noy, and J. Urrutia, Flipping edges in triangulations,Proc. 12th Ann. Symp. on Computational Geometry, Philadelphia, PA, 1996, pp. 214–223.
[K] M. Keil, Computing a subgraph of the minimum weight triangulation,Comput. Geom. Theory Appl. 4 (1994), 13–26.
[L] E. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, 1976.
[LK1] C. Levcopoulos and D. Krznaric, The greedy triangulation can be computed from the Delaunay in linear time, Tech. Report LU-CS-TR:94-136, Dept. of Computer Science and Numer. Analysis, Lund University, Lund, Sweden, 1994.
[LK2] C. Levcopoulos and D. Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation,Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 1996, pp. 392–401.
[T] R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1987.
[X] Y.-F. Xu, Minimum weight triangulation problem of a planar point set, Ph.D. Thesis, Institute of Applied Mathematics, Academia Sinica, Beijing, 1992.
[YXY] B.-T. Yang, Y.-F. Xu, and Z.-Y. You, A chain decomposition algorithm for the proof of a property on minimum weight triangulations,Proc. 5th Internat. Symp. on Algorithms and Computation (ISAAC'94), Lecture Notes in Computer Science, Vol. 834, Springer-Verlag, Berlin, 1994, pp. 423–427.
[Y] P. Yoeli, Compilation of data for computer-assisted relief cartography, in: J. C. Davis and M. J. McCullagh (eds.),Display and Analysis of Spatial Data, Wiley, New York, 1975, pp. 352–367.
Author information
Authors and Affiliations
Additional information
This research was supported by the Spezialforschungsbereich F003,Optimierung und Kontrolle. The research of Oswin Aichholzer was partially supported by the Austrian Ministry of Science and the Jubiläumsfond der Österreichischen Nationalbank. The research of Siu-Wing Cheng was partially supported by RGC Grant HKUST 190/93E. The research of Yin-Feng Xu was partially supported by RGC Grants HKUST 190/93E and HKUST 181/93E. Part of the work was done while Yin-Feng Xu visited the Department of Computer Science at the Hong Kong University of Science and Technology and the Institute for Theoretical Computer Science, Graz University of Technology.
Rights and permissions
About this article
Cite this article
Aichholzer, O., Aurenhammer, F., Cheng, SW. et al. Triangulations intersect nicely. Discrete Comput Geom 16, 339–359 (1996). https://doi.org/10.1007/BF02712872
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02712872