Abstract
Let T be a triangulation of a simple polygon. A flip in T is the operation of removing one diagonal of T and adding a different one such that the resulting graph is again a triangulation. The flip distance between two triangulations is the smallest number of flips required to transform one triangulation into the other. For the special case of convex polygons, the problem of determining the shortest flip distance between two triangulations is equivalent to determining the rotation distance between two binary trees, a central problem which is still open after over 25 years of intensive study.
We show that computing the flip distance between two triangulations of a simple polygon is NP-complete. This complements a recent result that shows APX-hardness of determining the flip distance between two triangulations of a planar point set.
O.A. partially supported by the ESF EUROCORES programme EuroGIGA - ComPoSe, Austrian Science Fund (FWF): I 648-N18. W.M. supported in part by DFG project MU/3501/1. A.P. is recipient of a DOC-fellowship of the Austrian Academy of Sciences at the Institute for Software Technology, Graz University of Technology.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abel, Z., Ballinger, B., Bose, P., Collette, S., Dujmović, V., Hurtado, F., Kominers, S., Langerman, S., Pór, A., Wood, D.: Every large point set contains many collinear points or an empty pentagon. Graphs Combin. 27, 47–60 (2011)
Aichholzer, O., Mulzer, W., Pilz, A.: Flip Distance Between Triangulations of a Simple Polygon is NP-Complete. ArXiv e-prints (2012) arXiv:1209.0579 [cs.CG]
Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60–80 (2009)
Culik II, K., Wood, D.: A note on some tree similarity measures. Inf. Process. Lett. 15(1), 39–42 (1982)
Eppstein, D.: Happy endings for flip graphs. JoCG 1(1), 3–28 (2010)
Hanke, S., Ottmann, T., Schuierer, S.: The edge-flipping distance of triangulations. J. UCS 2(8), 570–579 (1996)
Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22, 333–346 (1999)
Hwang, F., Richards, D., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics (1992)
Lawson, C.L.: Transforming triangulations. Discrete Math. 3(4), 365–372 (1972)
Lawson, C.L.: Software for C 1 surface interpolation. In: Rice, J.R. (ed.) Mathematical Software III, pp. 161–194. Academic Press, NY (1977)
Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point-set is NP-complete. In: Proc. 24th CCCG, pp. 127–132 (2012)
Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. ArXiv e-prints (2012) arXiv:1206.3179 [cs.CG]
Rao, S.K., Sadayappan, P., Hwang, F.K., Shor, P.W.: The rectilinear Steiner arborescence problem. Algorithmica 7, 277–288 (1992)
Shi, W., Su, C.: The rectilinear Steiner arborescence problem is NP-complete. In: Proc. 11th SODA, pp. 780–787 (2000)
Sleator, D., Tarjan, R., Thurston, W.: Rotation distance, triangulations and hyperbolic geometry. J. Amer. Math. Soc. 1, 647–682 (1988)
Trubin, V.: Subclass of the Steiner problems on a plane with rectilinear metric. Cybernetics 21, 320–324 (1985)
Urrutia, J.: Algunos problemas abiertos. In: Proc. IX Encuentros de Geometría Computacional, pp. 13–24 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aichholzer, O., Mulzer, W., Pilz, A. (2013). Flip Distance between Triangulations of a Simple Polygon is NP-Complete. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)