{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:57:20Z","timestamp":1775069840154,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>\n            A triangulation of a planar point set\n            <jats:italic>S<\/jats:italic>\n            is a maximal plane straight-line graph with vertex set\n            <jats:italic>S<\/jats:italic>\n            . In the\n            <jats:italic>minimum-weight triangulation<\/jats:italic>\n            (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard, using a reduction from PLANAR 1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using dynamic programming on polygonal faces, as well as the \u03b2-skeleton heuristic to certify that certain edges belong to the minimum-weight triangulation.\n          <\/jats:p>","DOI":"10.1145\/1346330.1346336","type":"journal-article","created":{"date-parts":[[2008,5,15]],"date-time":"2008-05-15T18:28:05Z","timestamp":1210876085000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":96,"title":["Minimum-weight triangulation is NP-hard"],"prefix":"10.1145","volume":"55","author":[{"given":"Wolfgang","family":"Mulzer","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, New Jersey"}]},{"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2008,5,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00018-6"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90016-Y"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276895"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237425"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573962"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Bern M. W. and Eppstein D. 1992. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry D.-Z. Du and F. K.-M. Hwang Eds. Number 1 in Lecture Notes Series on Computing. World Scientific River Edge NJ 23--90.  Bern M. W. and Eppstein D. 1992. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry D.-Z. Du and F. K.-M. Hwang Eds. Number 1 in Lecture Notes Series on Computing. World Scientific River Edge NJ 23--90.","DOI":"10.1142\/9789814355858_0002"},{"key":"e_1_2_2_7_1","first-page":"296","article-title":"Approximation algorithms for geometric problems. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, Ed. PWS Publishing, Boston, MA","volume":"8","author":"Bern M. W.","year":"1996","journal-title":"Chap."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185434"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000979"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 7th Canadian Conference on Computational Geometry (Quebec City, Que., Canada). 279--284","author":"Cheng S.-W."},{"key":"e_1_2_2_11_1","volume-title":"ISAAC '96: Proceedings of the 7th International Symposium on Algorithms and Computation","volume":"1178","author":"Cheng S.-W."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237360"},{"key":"e_1_2_2_13_1","volume-title":"Lecture Notes in Computer Science","volume":"401","author":"Das G."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009320"},{"key":"e_1_2_2_16_1","volume-title":"Tech. Rep. IIG-408","author":"Drysdale R.","year":"1995"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00236-5"},{"key":"e_1_2_2_18_1","first-page":"423","article-title":"Automatische Interpolation von Isolinien bei willk\u00fcrlich verteilten St\u00fctzpunkten","volume":"77","author":"D\u00fcppe R.-D.","year":"1970","journal-title":"Allgemeine Vermessungs-Nachrichten"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913058"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574002"},{"key":"e_1_2_2_21_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co. New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co. New York."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.11.006"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077476"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/179228.179230"},{"key":"e_1_2_2_26_1","unstructured":"Kellerer H. Pferschy U. and Pisinger D. 2007. Knapsack Problems. Springer-Verlag Berlin Germany.  Kellerer H. Pferschy U. and Pisinger D. 2007. Knapsack Problems. Springer-Verlag Berlin Germany."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90062-9"},{"key":"e_1_2_2_28_1","volume-title":"Colloq.","author":"Klincsek G. T.","year":"1980"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405033"},{"key":"e_1_2_2_30_1","volume-title":"ISAAC '97: Proceedings of the 8th International Symposium on Algorithms and Computation","volume":"1350","author":"Kyoda Y."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90170-0"},{"key":"e_1_2_2_32_1","volume-title":"SODA '96: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Levcopoulos C."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.21"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90104-2"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137859"},{"key":"e_1_2_2_37_1","volume-title":"Tech. Rep. B05-23 (revised)","author":"Mulzer W.","year":"2007"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90020-4"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132563"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220326"},{"key":"e_1_2_2_42_1","volume-title":"Proceedings of the 16th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Shamos M. I."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00008-6"},{"key":"e_1_2_2_44_1","volume-title":"ISAAC '94: Proceedings of the 5th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science","volume":"834","author":"Yang B.-T."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346336","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1346330.1346336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:58Z","timestamp":1750253938000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1145\/1346330.1346336"],"URL":"https:\/\/doi.org\/10.1145\/1346330.1346336","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}