{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:51:56Z","timestamp":1743133916827,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319388502"},{"type":"electronic","value":"9783319388519"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_10","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T15:33:54Z","timestamp":1464708834000},"page":"134-149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing Nonsimple Polygons of Minimum Perimeter"],"prefix":"10.1007","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Haas","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Hemmer","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Hoffmann","sequence":"additional","affiliation":[]},{"given":"Irina","family":"Kostitsyna","sequence":"additional","affiliation":[]},{"given":"Dominik","family":"Krupke","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Maurer","sequence":"additional","affiliation":[]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[]},{"given":"Arne","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Christiane","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Julian","family":"Troegel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1137\/S0097539700366115","volume":"31","author":"E Althaus","year":"2001","unstructured":"Althaus, E., Mehlhorn, K.: Traveling salesman-based curve reconstruction in polynomial time. SIAM J. Comput. 31(1), 27\u201366 (2001)","journal-title":"SIAM J. Comput."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: On the solution of traveling salesman problems. Documenta Mathematica \u2013 Journal der DeutschenMathematiker-Vereinigung, ICM, pp. 645\u2013656 (1998)","DOI":"10.4171\/dms\/1-3\/62"},{"key":"10_CR3","series-title":"Princeton Series in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1515\/9781400841103","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"DL Applegate","year":"2007","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2007)"},{"issue":"5","key":"10_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"1\u20134","key":"10_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01553881","volume":"4","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: Constrained Delaunay triangulations. Algorithmica 4(1\u20134), 97\u2013108 (1989)","journal-title":"Algorithmica"},{"key":"10_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the Travelling Salesman Problem, Technical report 388, Graduate School of Industrial Administration, CMU (1976)"},{"key":"10_CR7","volume-title":"In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation","author":"WJ Cook","year":"2012","unstructured":"Cook, W.J.: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton (2012)"},{"key":"10_CR8","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)"},{"issue":"4","key":"10_CR9","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0925-7721(99)00051-6","volume":"15","author":"TK Dey","year":"2000","unstructured":"Dey, T.K., Mehlhorn, K., Ramos, E.A.: Curve reconstruction: connecting dots with good reason. Comput. Geom. 15(4), 229\u2013244 (2000)","journal-title":"Comput. Geom."},{"issue":"3","key":"10_CR10","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0020-0190(87)90124-4","volume":"25","author":"MB Dillencourt","year":"1987","unstructured":"Dillencourt, M.B.: A non-Hamiltonian, nondegenerate Delaunay triangulation. Inf. Process. Lett. 25(3), 149\u2013151 (1987)","journal-title":"Inf. Process. Lett."},{"key":"10_CR11","unstructured":"Fekete, S.P., Friedrichs, S., Hemmer, M., Papenberg, M., Schmidt, A., Troegel, J.: Area- and boundary-optimal polygonalization of planar point sets. In: EuroCG 2015, pp. 133\u2013136 (2015)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Haas, A., Hemmer, M., Hoffmann, M., Kostitsyna, I., Krupke, D., Maurer, F., Mitchell, J.S.B., Schmidt, A., Schmidt, C., Troegel, J.: Computing nonsimple polygons of minimum perimeter. CoRR, abs\/1603.07077 (2016)","DOI":"10.1007\/978-3-319-38851-9_10"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Giesen, J.: Curve reconstruction, the traveling salesman problem and Menger\u2019s theorem on length. In: Proceedings of 15th Annual Symposium on Computational Geometry (SoCG), pp. 207\u2013216 (1999)","DOI":"10.1145\/304893.304973"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0120887","volume":"12","author":"M Gr\u00f6tschel","year":"1980","unstructured":"Gr\u00f6tschel, M.: On the symmetric travelling salesman problem: solution of a 120-city problem. Math. Program. Study 12, 61\u201377 (1980)","journal-title":"Math. Program. Study"},{"key":"10_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/b101971","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, New York (2007)"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. In: Handbooks in Operations Research and Management Science, vol. 7, pp. 225\u2013330 (1995)","DOI":"10.1016\/S0927-0507(05)80121-5"},{"key":"10_CR17","unstructured":"Land, A.: The solution of some 100-city Travelling Salesman Problems, Technical report, London School of Economics (1979)"},{"key":"10_CR18","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"EL Lawler","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498\u2013516 (1973)","journal-title":"Oper. Res."},{"issue":"4","key":"10_CR20","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR21","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60\u2013100 (1991)","journal-title":"SIAM Rev."},{"key":"10_CR22","unstructured":"Pferschy, U., Stanek, R.: Generating subtour constraints for the TSP from pure integer solutions. Department of Statistics and Operations Research, University of Graz, Technical report (2014)"},{"issue":"4","key":"10_CR23","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPlib - a traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"key":"10_CR24","unstructured":"Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., Zukerman, B.: 2D arrangements. In: CGAL User and Reference Manual, 4.3rd edn. CGAL Editorial Board (2014)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T17:55:14Z","timestamp":1692381314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"1 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}