{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:03:02Z","timestamp":1756425782668,"version":"3.44.0"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662273"},{"type":"electronic","value":"9783540485186"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48518-x_10","type":"book-chapter","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T13:57:15Z","timestamp":1195048635000},"page":"161-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Case Study on the Cost of Geometric Computing"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Schirra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,4,19]]},"reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0020-0190(79)90156-X","volume":"8","author":"S. G. Akl","year":"1979","unstructured":"S. G. Akl. Two remarks on a convex hull algorithm. Inform. Process. Lett., 8(2):108\u2013109, 1979.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10_CR2","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0020-0190(80)90070-8","volume":"10","author":"S. G. Akl","year":"1980","unstructured":"S. G. Akl. Corrigendum on convex hull algorithms. Inform. Process. Lett., 10(3):168, 1980.","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(78)90003-0","volume":"7","author":"S. G. Akl","year":"1978","unstructured":"S. G. Akl and G. T. Toussaint. A fast convex hull algorithm. Inform. Process. Lett., 7(5):219\u2013222, 1978.","journal-title":"Inform. Process. Lett."},{"key":"10_CR4","volume-title":"Introduction to Interval Computation","author":"G. Alefeld","year":"1983","unstructured":"G. Alefeld and J. Herzberger. Introduction to Interval Computation. Academic Press, New York, 1983."},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934510","volume":"24","author":"D. C. S. Allison","year":"1984","unstructured":"D. C. S. Allison and M. T. Noga. Some performance tests of convex hull algorithms. BIT, 24:2\u201313, 1984.","journal-title":"BIT"},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(78)90041-8","volume":"7","author":"K. R. Anderson","year":"1978","unstructured":"K. R. Anderson. A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 7(1):53\u201355, 1978.","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10_CR7","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"A. M. Andrew","year":"1979","unstructured":"A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inform. Process. Lett., 9(5):216\u2013219, 1979.","journal-title":"Inform. Process. Lett."},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/0262-8856(83)90065-3","volume":"1","author":"B. K. Bhattacharya","year":"1983","unstructured":"B. K. Bhattacharya and G. T. Toussaint. Time-and storage-efficient implementation of an optimal convex hull algorithm. Image Vision Comput., 1:140\u2013144, 1983.","journal-title":"Image Vision Comput."},{"key":"10_CR9","series-title":"Technical Report","volume-title":"Robust plane sweep for intersecting segments","author":"J.-D. Boissonnat","year":"1997","unstructured":"J.-D. Boissonnat and F. Preparata. Robust plane sweep for intersecting segments. Technical Report 3270, INRIA, Sophia-Antipolis, France, September 1997."},{"key":"10_CR10","unstructured":"K. Briggs. The doubledouble home page. http:\/\/epidem13.plantsci.cam.ac.uk\/~kbriggs\/doubledouble.html."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 165\u2013174, 1998.","DOI":"10.1145\/276884.276903"},{"key":"10_CR12","unstructured":"C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra. A strong and easily computable separation bound for arithmetic expressions involving square roots. In Proc. of the 8th ACM-SIAM Symp. on Discrete Algorithms, pages 702\u2013709, 1997."},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"C. Burnikel, J. K\u00f6nemann, K. Mehlhorn, S. N\u00e4her, S. Schirra, and C. Uhrig. Exact geometric computation in LEDA. In Proceedings of the 11th ACM Symposium on Computational Geometry, pages C18\u2013C19, 1995.","DOI":"10.1145\/220279.220330"},{"key":"10_CR14","unstructured":"C. Burnikel, K. Mehlhorn, and S. Schirra. The LEDA class real number. Technical Report MPI-I-96-1-001, Max-Planck-Institut f\u00fcr Informatik, 1996."},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/0020-0190(78)90021-2","volume":"7","author":"A. Bykat","year":"1978","unstructured":"A. Bykat. Convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 7:296\u2013298, 1978.","journal-title":"Inform. Process. Lett."},{"key":"10_CR16","unstructured":"CGAL project. http:\/\/www.cs.uu.nl\/CGAL"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"T. M. Y. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 10\u201319, 1995.","DOI":"10.1145\/220279.220281"},{"key":"10_CR18","unstructured":"K. Clarkson. A short, complete planar convex hull code. http:\/\/cm.bell-labs.com\/who\/clarkson\/2dch.c."},{"key":"10_CR19","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/BF01397083","volume":"18","author":"T. J. Dekker","year":"1971","unstructured":"T. J. Dekker. A floating-point technique for extending the available precision. Numerische Mathematik, 18:224\u2013242, 1971.","journal-title":"Numerische Mathematik"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0020-0190(79)90056-5","volume":"9","author":"F. D\u00e9vai","year":"1979","unstructured":"F. D\u00e9vai and T. Szendr\u00e9nyi. Comments on convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 9:141\u2013142, 1979.","journal-title":"Inform. Process. Lett."},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1145\/355759.355766","volume":"3","author":"W. F. Eddy","year":"1977","unstructured":"W. F. Eddy. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw., 3:398\u2013403 and 411\u2013412, 1977.","journal-title":"ACM Trans. Math. Softw."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Verlag, 1986.","DOI":"10.1007\/978-3-642-61568-9"},{"issue":"3","key":"10_CR23","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/231731.231735","volume":"15","author":"S. Fortune","year":"1996","unstructured":"S. Fortune and C. Van Wyk. Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Transactions on Graphics, 15(3):223\u2013248, 1996.","journal-title":"ACM Transactions on Graphics"},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0020-0190(79)90015-2","volume":"8","author":"A. Fournier","year":"1979","unstructured":"A. Fournier. Comments on convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 8:173, 1979.","journal-title":"Inform. Process. Lett."},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 1:132\u2013133, 1972.","journal-title":"Inform. Process. Lett."},{"key":"10_CR26","unstructured":"T. Granlund. GNU MP, The GNU Multiple Precision Arithmetic Library, 2.0.2 edition, June 1996."},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1093\/comjnl\/22.3.262","volume":"22","author":"P. J. Green","year":"1979","unstructured":"P. J. Green and B. W. Silverman. Constructing the convex hull of a set of points in the plane. Comput. J., 22:262\u2013266, 1979.","journal-title":"Comput. J."},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0262-8856(85)90040-X","volume":"3","author":"C. C. Handley","year":"1985","unstructured":"C. C. Handley. Efficient planar convex hull algorithm. Image Vision Comput., 3:29\u201335, 1985.","journal-title":"Image Vision Comput."},{"key":"10_CR29","volume-title":"An almost trivial convex hull algorithm for a presorted point set in the plane","author":"S. Hertel","year":"1983","unstructured":"S. Hertel. An almost trivial convex hull algorithm for a presorted point set in the plane. Report A83\/08, Fachber. Inform., Univ. Saarlandes, Saarbr\u00fccken, West Germany, 1983."},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"R. A. Jarvis","year":"1973","unstructured":"R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Inform. Process. Lett., 2:18\u201321, 1973.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"10_CR31","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/99902.99905","volume":"10","author":"M. Karasick","year":"1991","unstructured":"M. Karasick, D. Lieber, and L.R. Nackman. Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics, 10(1):71\u201391, 1991.","journal-title":"ACM Transactions on Graphics"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM J. Comput., 15:287\u2013299, 1986.","journal-title":"SIAM J. Comput."},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0020-0190(78)90042-X","volume":"7","author":"J. Koplowitz","year":"1978","unstructured":"J. Koplowitz and D. Jouppi. A more efficient convex hull algorithm. Inform. Process. Lett., 7:56\u201357, 1978.","journal-title":"Inform. Process. Lett."},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"G. Liotta, F. P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 156\u2013165, 1997.","DOI":"10.1145\/262839.262922"},{"key":"10_CR35","volume-title":"C++ primer","author":"S. B. Lippman","year":"1998","unstructured":"S. B. Lippman and J. Lajoie. C++ primer. Addison-Wesley, Reading, MA, 3rd ed., 1998.","edition":"3rd ed."},{"key":"10_CR36","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0167-8655(85)90039-X","volume":"3","author":"M. M. McQueen","year":"1985","unstructured":"M. M. McQueen and G. T. Toussaint. On the ultimate convex hull algorithm in practice. Pattern Recogn. Lett., 3:29\u201334, 1985.","journal-title":"Pattern Recogn. Lett."},{"key":"10_CR37","series-title":"Data Structures and Algorithms","volume-title":"Multi-dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Multi-dimensional Searching and Computational Geometry, volume 3 of Data Structures and Algorithms. Springer-Verlag, Heidelberg, Germany, 1984."},{"key":"10_CR38","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K. Mehlhorn","year":"1995","unstructured":"K. Mehlhorn and S. N\u00e4her. LEDA, a platform for combinatorial and geometric computing. Communications of the ACM, 38:96\u2013102, 1995.","journal-title":"Communications of the ACM"},{"key":"10_CR39","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, S. N\u00e4her, M. Seel, and C. Uhrig. The LEDA User manual, 3.7 edition, 1998. see http:\/\/www.mpi-sb.mpg.de\/LEDA\/leda.html.","DOI":"10.1007\/3-540-63165-8_161"},{"key":"10_CR40","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970906","volume-title":"Methods and Applications of Interval Analysis","author":"R. E. Moore","year":"1979","unstructured":"R. E. Moore. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979."},{"key":"10_CR41","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0020-0190(80)90142-8","volume":"10","author":"M. H. Overmars","year":"1980","unstructured":"M. H. Overmars and J. van Leeuwen. Further comments on Bykat\u2019s convex hull algorithm. Inform. Process. Lett., 10:209\u2013212, 1980.","journal-title":"Inform. Process. Lett."},{"key":"10_CR42","unstructured":"D. M. Priest. On Properties of Floating-Point Arithmetic: Numerical Stability and the Cost of Accurate Computations. PhD thesis, Department of Mathematics, University of California at Berkeley, 1992."},{"key":"10_CR43","unstructured":"J. R. Shewchuk. C code for the 2d and 3d orientation and incircle tests, and for arbitrary precision floating-point addition and multiplication. Available from http:\/\/www.cs.cmu.edu\/~quake\/robust.html."},{"key":"10_CR44","unstructured":"J. R. Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Technical Report CMU-CS-96-140, School of Computer Science, Carnegie Mellon University, 1996."},{"key":"10_CR45","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0167-8655(85)90038-8","volume":"3","author":"G. T. Toussaint","year":"1985","unstructured":"G. T. Toussaint. A historical note on convex hull finding algorithms. Pattern Recogn. Lett., 3:21\u201328, 1985.","journal-title":"Pattern Recogn. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experimentation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48518-X_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T07:51:34Z","timestamp":1756367494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48518-X_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662273","9783540485186"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-48518-x_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"19 April 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}