{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T03:06:20Z","timestamp":1782183980935,"version":"3.54.5"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00453-008-9174-2","type":"journal-article","created":{"date-parts":[[2008,3,3]],"date-time":"2008-03-03T16:51:51Z","timestamp":1204563111000},"page":"235-269","source":"Crossref","is-referenced-by-count":75,"title":["Largest and Smallest Convex Hulls for Imprecise Points"],"prefix":"10.1007","volume":"56","author":[{"given":"Maarten","family":"L\u00f6ffler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"van Kreveld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,3,4]]},"reference":[{"key":"9174_CR1","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0020-0190(99)00107-6","volume":"71","author":"M. Abellanas","year":"1999","unstructured":"Abellanas, M., Hurtado, F., Ramos, P.A.: Structural tolerance and Delaunay triangulation. Inf. Process. Lett. 71, 221\u2013227 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9174_CR2","unstructured":"Bandyopadhyay, D., Snoeyink, J.: Almost-Delaunay simplices: nearest neighbour relations for imprecise points. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0410\u2013419 (2004)"},{"key":"9174_CR3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF02187906","volume":"3","author":"C. Bajaj","year":"1988","unstructured":"Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3, 177\u2013191 (1988)","journal-title":"Discrete Comput. Geom."},{"key":"9174_CR4","unstructured":"Barber, B.C.: Computational geometry with imprecise data and arithmetic. TR-377-91, Ph.D. Thesis, Princeton University, Department of Computer Science (1993)"},{"key":"9174_CR5","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., Lazard, S.: Convex hulls of bounded curvature. In: Proceedings of the 8th Canadian Conference on Computational Geometry, pp.\u00a014\u201319 (1996)","DOI":"10.1515\/9780773591134-005"},{"key":"9174_CR6","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1142\/S0218195997000326","volume":"7","author":"L. Cai","year":"1997","unstructured":"Cai, L., Keil, J.M.: Computing visibility information in an inaccurate simple polygon. Int. J. Comput. Geom. Appl. 7, 515\u2013538 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"9174_CR7","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M. Berg de","year":"2005","unstructured":"de\u00a0Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van\u00a0der\u00a0Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22\u201336 (2005)","journal-title":"J. Algorithms"},{"key":"9174_CR8","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1142\/S0218195998000242","volume":"8","author":"M. Berg de","year":"1998","unstructured":"de\u00a0Berg, M., Meijer, H., Overmars, M.H., Wilfong, G.T.: Computing the angularity tolerance. Int. J. Comput. Geom. Appl. 8, 467\u2013482 (1998)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9174_CR9","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/0010-4485(93)90070-5","volume":"25","author":"H. Desaulniers","year":"1993","unstructured":"Desaulniers, H., Stewart, N.F.: Robustness of numerical methods in geometric computation when problem data is uncertain. Comput. Aided Des. 25, 539\u2013545 (1993)","journal-title":"Comput. Aided Des."},{"key":"9174_CR10","doi-asserted-by":"crossref","unstructured":"Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proceedings of the 35th ACM Symposium on Theory of Computing, pp.\u00a0473\u2013482 (2003)","DOI":"10.1145\/780611.780612"},{"key":"9174_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(85)90005-2","volume":"35","author":"H. Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H.: Finding transversals for sets of simple geometric figures. Theor. Comput. Sci. 35, 55\u201369 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9174_CR12","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.dam.2004.02.018","volume":"145","author":"J. Fiala","year":"2005","unstructured":"Fiala, J., Kratochvil, J., Proskurowski, A.: Systems of distant representatives. Discrete Appl. Math. 145, 306\u2013316 (2005)","journal-title":"Discrete Appl. Math."},{"key":"9174_CR13","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M. Garey","year":"1977","unstructured":"Garey, M., Graham, R., Johnson, D.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32, 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"9174_CR14","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/0734-189X(90)90135-I","volume":"49","author":"M.T. Goodrich","year":"1990","unstructured":"Goodrich, M.T., Snoeyink, J.: Stabbing parallel segments with a convex polygon. Comput. Vis. Graph. Image Process. 49, 152\u2013170 (1990)","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"9174_CR15","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1007\/BF01190154","volume":"9","author":"L. Guibas","year":"1993","unstructured":"Guibas, L., Salesin, D., Stolfi, J.: Constructing strongly convex approximate hulls with inaccurate primitives. Algorithmica 9, 534\u2013560 (1993)","journal-title":"Algorithmica"},{"key":"9174_CR16","unstructured":"Khanban, A.A., Edalat, A.: Computing Delaunay triangulation with imprecise input data. In: Proceedings of the 15th Canadian Conference on Computational Geometry, pp.\u00a094\u201397 (2003)"},{"key":"9174_CR17","series-title":"LNCS","first-page":"447","volume-title":"Proceedings of the 10th Workshop on Algorithms and Data Structures","author":"M. Kreveld van","year":"2007","unstructured":"van\u00a0Kreveld, M., L\u00f6ffler, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. In: Proceedings of the 10th Workshop on Algorithms and Data Structures. LNCS, vol.\u00a04619, pp.\u00a0447\u2013458. Springer, Berlin (2007)"},{"key":"9174_CR18","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01758851","volume":"8","author":"Z. Li","year":"1992","unstructured":"Li, Z., Milenkovic, V.: Constructing strongly convex hulls using exact or rounded arithmetic. Algorithmica 8, 345\u2013364 (1992)","journal-title":"Algorithmica"},{"key":"9174_CR19","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-540-77918-6_8","volume-title":"Proceedings of the 5th Workshop on Approximation and Online Algorithms","author":"M. L\u00f6ffler","year":"2008","unstructured":"L\u00f6ffler, M., van\u00a0Kreveld, M.: Approximating largest convex hulls for imprecise points. In: Proceedings of the 5th Workshop on Approximation and Online Algorithms. LNCS, vol.\u00a04927, pp.\u00a089\u2013102. Springer, Berlin (2008)"},{"key":"9174_CR20","doi-asserted-by":"crossref","unstructured":"Mata, C., Mitchell, J.S.: Approximation algorithms for geometric tour and network design problems. In: Proceedings of the 11th ACM Symposium on Computational Geometry, pp.\u00a0360\u2013369 (1995)","DOI":"10.1145\/220279.220318"},{"issue":"2","key":"9174_CR21","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.ipl.2007.08.029","volume":"105","author":"A. Mukhopadhyay","year":"2008","unstructured":"Mukhopadhyay, A., Kumar, C., Greene, E., Bhattacharya, B.: On intersecting a set of parallel line segments with a convex polygon of minimum area. Inf. Process. Lett. 105(2), 58\u201364 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9174_CR22","series-title":"LNCS","first-page":"252","volume-title":"Proceedings of the 4th Japanese Conference on Discrete and Computational Geometry","author":"T. Nagai","year":"2000","unstructured":"Nagai, T., Tokura, N.: Tight error bounds of geometric problems on convex objects with imprecise coordinates. In: Proceedings of the 4th Japanese Conference on Discrete and Computational Geometry. LNCS, vol.\u00a02098, pp.\u00a0252\u2013263. Springer, Berlin (2000)"},{"issue":"3","key":"9174_CR23","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1142\/S0218195995000143","volume":"5","author":"D. Rappaport","year":"1995","unstructured":"Rappaport, D.: Minimum polygon transversals of line segments. Int. J. Comput. Geom. Appl. 5(3), 243\u2013256 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9174_CR24","unstructured":"O\u2019Rourke, J.: Sum of Square Roots. http:\/\/maven.smith.edu\/~orourke\/TOPP\/P33.html"},{"key":"9174_CR25","unstructured":"Ostrovsky-Berman, Y., Joskowicz, L.: Uncertainty envelopes. In: Proceedings of the 21st European Workshop on Computational Geometry, pp.\u00a0175\u2013178 (2005)"},{"key":"9174_CR26","unstructured":"Polishchuk, V., Mitchell, J.S.B.: Touring convex bodies\u2014a conic programming solution. In: Proceedings of the 17th Canadian Conference on Computational Geometry, pp.\u00a0290\u2013293 (2005)"},{"key":"9174_CR27","series-title":"LNCS","first-page":"446","volume-title":"Proceedings of the European Symposium on Algorithms","author":"S. Safra","year":"2003","unstructured":"Safra, S., Schwartz, O.: On the complexity of approximating TSP with neighborhoods and related problems. In: Proceedings of the European Symposium on Algorithms. LNCS, vol.\u00a02832, pp.\u00a0446\u2013458. Springer, Berlin (2003)"},{"key":"9174_CR28","doi-asserted-by":"crossref","first-page":"1577","DOI":"10.1137\/S0097539798340205","volume":"29","author":"J. Sellen","year":"2000","unstructured":"Sellen, J., Choi, J., Yap, C.-K.: Precision-sensitive Euclidean shortest paths in 3-space. SIAM J. Comput. 29, 1577\u20131595 (2000)","journal-title":"SIAM J. Comput."},{"key":"9174_CR29","unstructured":"Toussaint, G.T.: Solving geometric problems with the rotating calipers. In: Proceedings of the IEEE Mediterranean Electrotechnical Conference (1983)"},{"key":"9174_CR30","first-page":"927","volume-title":"Handbook of Discrete and Computational Geometry","author":"C.-K. Yap","year":"2004","unstructured":"Yap, C.-K.: Robust geometric computation. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp.\u00a0927\u2013952. Chapman & Hall\/CRC, Boca Raton (2004). Chap.\u00a041"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9174-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T02:07:16Z","timestamp":1708654036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9174-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,4]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9174"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9174-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,4]]}}}