{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:39:43Z","timestamp":1787506783937,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441809","type":"print"},{"value":"9783540457497","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45749-6_20","type":"book-chapter","created":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T11:42:44Z","timestamp":1183549364000},"page":"187-199","source":"Crossref","is-referenced-by-count":4,"title":["TSP with Neighborhoods of Varying Size"],"prefix":"10.1007","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark H.","family":"Overmars","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"van Frank der Stappen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0925-7721(95)00005-8","volume":"5","author":"P. Agarwal","year":"1995","unstructured":"P. Agarwal, M. Katz and M. Sharir. Computing depth orders for fat objects and related problems. Computational Geometry-Theory & Appl., 5:187\u2013206, 1995.","journal-title":"Computational Geometry-Theory & Appl."},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/BF01758853","volume":"8","author":"H. Alt","year":"1992","unstructured":"H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. N\u00e4her, S. Schirra and C. Uhrig. Approximate motion planning and the complexity of the boundary of the union of simple geometric figures. Algorithmica, 8:391\u2013406, 1992.","journal-title":"Algorithmica"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E.M. Arkin","year":"1994","unstructured":"E.M. Arkin and R. Hassin. Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics, 55:197\u2013218, 1994.","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"20_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753\u2013782, 1998.","journal-title":"Journal of the ACM"},{"key":"20_CR5","unstructured":"P. Berman and M. Karpinski. On some tighter inapproximability results. Technical Report 98-029, ECCC, 1998."},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"L.P. Chew, H. David, M. J. Katz and K. Kedem. Walking around fat obstacles. Information Processing Letters, to appear.","DOI":"10.1016\/S0020-0190(01)00321-0"},{"key":"20_CR7","unstructured":"A. Dumitrescu and J. S. B. Mitchell. Approximation algorithms for TSP with neighborhoods in the plane. In Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"M.R. Garey, R. L. Graham and D. S. Johnson. Some NP-complete geometric problems. In Proc. 8th Annual ACM Symposium on Theory of Computing, 1976.","DOI":"10.1145\/800113.803626"},{"key":"20_CR9","first-page":"469","volume":"6","author":"J. Gudmundsson","year":"1999","unstructured":"J. Gudmundsson and C. Levcopoulos. A fast approximation algorithm for TSP with neighborhoods. Nordic Journal of Computing, 6:469\u2013488, 1999.","journal-title":"Nordic Journal of Computing"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1006\/jagm.1995.1017","volume":"18","author":"J. Hershberger","year":"1995","unstructured":"J. Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms, 18:403\u2013431, 1995.","journal-title":"Journal of Algorithms"},{"key":"20_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/3-540-57155-8_270","volume-title":"On fat partitioning, fat covering, and the union size of polygons","author":"M. Kreveld van","year":"1993","unstructured":"M. van Kreveld. On fat partitioning, fat covering, and the union size of polygons. In Proc. 3rd Workshop on Algorithms and Data Structures, volume 709 of Lecture Notes in Computer Science, pages 452\u2013463. Springer-Verlag, 1993."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"C. Mata and J. S.B. Mitchell. Approximation algorithms for geometric tour and network design problems. In Proc. 11th Annual ACM Symposium on Computational Geometry, pages 360\u2013369, 1995.","DOI":"10.1145\/220279.220318"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, N. Miller, J. Pach, M. Sharir, S. Sifrony and E. Welzl. Fat triangles determine linearly many holes. In Proc. 32nd Annual Annual IEEE Symposium on Foundations of Computer Science, pages 49\u201358, 1991.","DOI":"10.1109\/SFCS.1991.185347"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry, Elsevier Science.","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"issue":"4","key":"20_CR15","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J. S. B. Mitchell","year":"1999","unstructured":"J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal of Computing, 28(4):1298\u20131309, 1999.","journal-title":"SIAM Journal of Computing"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C. H. Papadimitriou","year":"1977","unstructured":"C. H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science, 4:237\u2013244, 1977.","journal-title":"Theoretical Computer Science"},{"key":"20_CR17","series-title":"Lect Notes Comput Sci","first-page":"196","volume-title":"Beyond Steiner\u2019s problem: A VLSI oriented generalization","author":"G. Reich","year":"1989","unstructured":"G. Reich and P. Widmayer. Beyond Steiner\u2019s problem: A VLSI oriented generalization.In Proc. 15th Internat. Workshop Graph-Theoret. Concepts Comput. Sci., volume 411 of Lecture Notes in Comp. Sci., pages 196\u2013210, Springer-Verlag, 1989."},{"key":"20_CR18","unstructured":"O. Schwartz and S. Safra. On the complexity of approximating TSP with neighborhoods and related problems. Manuscript, 2002."},{"key":"20_CR19","unstructured":"B. Shaleooi. Algorithms for cutting sheets of metal. LUNDFD6\/NFCS-5189\/1-44\/2001, Master thesis, Department of Computer Science, Lund University, 2001."},{"key":"20_CR20","unstructured":"P. Slav\u00edk. The Errand Scheduling Problem. Technical report 97-02, Department of Computer Science and Engineering, SUNY Buffalo, 1997."},{"key":"20_CR21","volume-title":"Motion Planning amidst Fat Obstacles","author":"A. F. Stappen van der","year":"1994","unstructured":"A. F. van der Stappen. Motion Planning amidst Fat Obstacles, Ph.D. Dissertation, Department of Computer Science, Utrecht University, Utrecht, Netherlands, 1994."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45749-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T23:48:11Z","timestamp":1737157691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45749-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441809","9783540457497"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45749-6_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}