{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T03:25:52Z","timestamp":1783481152019,"version":"3.55.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,6,11]],"date-time":"2015-06-11T00:00:00Z","timestamp":1433980800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00454-015-9709-7","type":"journal-article","created":{"date-parts":[[2015,6,11]],"date-time":"2015-06-11T03:12:56Z","timestamp":1433992376000},"page":"368-389","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Flip Distance Between Triangulations of a Simple Polygon is NP-Complete"],"prefix":"10.1007","volume":"54","author":[{"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Pilz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,11]]},"reference":[{"key":"9709_CR1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s00373-010-0957-2","volume":"27","author":"Z Abel","year":"2011","unstructured":"Abel, Z., Ballinger, B., Bose, P., Collette, S., Dujmovi\u0107, V., Hurtado, F., Kominers, S., Langerman, S., P\u00f3r, A., Wood, D.: Every large point set contains many collinear points or an empty pentagon. Graphs Comb. 27, 47\u201360 (2011)","journal-title":"Graphs Comb."},{"key":"9709_CR2","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. In: Proceedings of 29th European Workshop on Computational Geometry, pp. 115\u2013118. EWCG, Braunschweig (2013)","DOI":"10.1007\/978-3-642-40450-4_2"},{"key":"9709_CR3","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. In: Bodlaender, H.L., Italiano, G.F. (eds.) Algorithms\u2014ESA 2013\u201421st Annual European Symposium, Sophia Antipolis, France, 2\u20134 September 2013. Lecture Notes in Computer Science, vol. 8125, pp. 13\u201324. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40450-4_2"},{"issue":"1","key":"9709_CR4","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.comgeo.2008.04.001","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60\u201380 (2009)","journal-title":"Comput. Geom."},{"key":"9709_CR5","doi-asserted-by":"crossref","unstructured":"Canny, J.F., Donald, B.R., Ressler, E.K.: A rational rotation method for robust geometric algorithms. In: Proceedings of 8th Annual ACM Symposium on Computational Geometry (SoCG 1992), pp. 251\u2013260. ACM Press, New York (1992)","DOI":"10.1145\/142675.142726"},{"issue":"1","key":"9709_CR6","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B Chazelle","year":"1985","unstructured":"Chazelle, B., Guibas, L.J., Lee, D.T.: The power of geometric duality. BIT 25(1), 76\u201390 (1985)","journal-title":"BIT"},{"issue":"1","key":"9709_CR7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(82)90083-7","volume":"15","author":"K Culik II","year":"1982","unstructured":"Culik II, K., Wood, D.: A note on some tree similarity measures. Inf. Process. Lett. 15(1), 39\u201342 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9709_CR8","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9709_CR9","first-page":"3","volume":"1","author":"D Eppstein","year":"2010","unstructured":"Eppstein, D.: Happy endings for flip graphs. J. Comput. Geom. 1(1), 3\u201328 (2010)","journal-title":"J. Comput. Geom."},{"issue":"8","key":"9709_CR10","first-page":"570","volume":"2","author":"S Hanke","year":"1996","unstructured":"Hanke, S., Ottmann, T., Schuierer, S.: The edge-flipping distance of triangulations. J. UCS 2(8), 570\u2013579 (1996)","journal-title":"J. UCS"},{"key":"9709_CR11","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/PL00009464","volume":"22","author":"F Hurtado","year":"1999","unstructured":"Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22, 333\u2013346 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9709_CR12","series-title":"Graduate Texts in Mathematics","volume-title":"Elliptic Curves","author":"D Husem\u00f6ller","year":"2003","unstructured":"Husem\u00f6ller, D.: Elliptic Curves. Graduate Texts in Mathematics. Springer-Verlag, New York (2003)"},{"key":"9709_CR13","series-title":"Annals of Discrete Mathematics","volume-title":"The Steiner Tree Problem","author":"F Hwang","year":"1992","unstructured":"Hwang, F., Richards, D., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics. North-Holland, Amsterdam (1992)"},{"key":"9709_CR14","unstructured":"Kanj, I.A., Xia, G.: Flip distance is in FPT time $$O(n+ k \\cdot c^k)$$ O ( n + k \u00b7 c k ) . (2014). http:\/\/arxiv.org\/abs\/1407.1525"},{"issue":"4","key":"9709_CR15","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0012-365X(72)90093-3","volume":"3","author":"CL Lawson","year":"1972","unstructured":"Lawson, C.L.: Transforming triangulations. Discrete Math. 3(4), 365\u2013372 (1972)","journal-title":"Discrete Math."},{"key":"9709_CR16","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/B978-0-12-587260-7.50011-X","volume-title":"Mathematical Software III","author":"CL Lawson","year":"1977","unstructured":"Lawson, C.L.: Software for $$C^1$$ C 1 surface interpolation. In: Rice, J.R. (ed.) Mathematical Software III, pp. 161\u2013194. Academic Press, New York (1977)"},{"issue":"3","key":"9709_CR17","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1023\/A:1009826311973","volume":"4","author":"B Lu","year":"2000","unstructured":"Lu, B., Ruan, L.: Polynomial time approximation scheme for the rectilinear Steiner arborescence problem. J. Comb. Optim. 4(3), 357\u2013363 (2000)","journal-title":"J. Comb. Optim."},{"key":"9709_CR18","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point-set is NP-complete. In: Proceedings of 24th Canadian Conference on Computational Geometry (CCCG), pp. 127\u2013132. CCCG, Charlottetown (2012)"},{"issue":"5","key":"9709_CR19","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.comgeo.2014.01.001","volume":"47","author":"A Pilz","year":"2014","unstructured":"Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom. 47(5), 589\u2013604 (2014)","journal-title":"Comput. Geom."},{"key":"9709_CR20","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01758762","volume":"7","author":"SK Rao","year":"1992","unstructured":"Rao, S.K., Sadayappan, P., Hwang, F.K., Shor, P.W.: The rectilinear Steiner arborescence problem. Algorithmica 7, 277\u2013288 (1992)","journal-title":"Algorithmica"},{"key":"9709_CR21","unstructured":"Shi, W., Su, C.: The rectilinear Steiner arborescence problem is NP-complete. In: Proceedings of 11th Symposium on Discrete Algorithms (SODA), pp. 780\u2013787. SODA, San Francisco (2000)"},{"key":"9709_CR22","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1090\/S0894-0347-1988-0928904-4","volume":"1","author":"D Sleator","year":"1988","unstructured":"Sleator, D., Tarjan, R., Thurston, W.: Rotation distance, triangulations and hyperbolic geometry. J. Am. Math. Soc. 1, 647\u2013682 (1988)","journal-title":"J. Am. Math. Soc."},{"key":"9709_CR23","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF01078826","volume":"21","author":"V Trubin","year":"1985","unstructured":"Trubin, V.: Subclass of the Steiner problems on a plane with rectilinear metric. Cybernetics 21, 320\u2013324 (1985)","journal-title":"Cybernetics"},{"key":"9709_CR24","unstructured":"Urrutia, J.: Algunos problemas abiertos. In: Proceedings of IX Encuentros de Geometr\u00eda Computacional, pp. 13\u201324. Universitat de Girona, Girona (2001)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9709-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9709-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9709-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T12:37:32Z","timestamp":1566823052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9709-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,11]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9709"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9709-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,11]]}}}