{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:18Z","timestamp":1787337498592,"version":"build-2736575974"},"reference-count":59,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact-computation paradigm and formalize the notion of degree of a geometric algorithm as a worst-case quantification of the precision (number of bits) to which arithmetic calculation have to be executed in order to guarantee topological correctness. We also propose a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm and an illustration of our general approach where algorithm design is driven also by the degree, we consider the important classical problem of proximity queries in two and three dimensions and develop a new technique for the efficient and robust execution of such queries based on an implicit representation of Voronoi diagrams. Our new technique offers both low degree and fast query time and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number of operations, and arithmetic degree.<\/jats:p>","DOI":"10.1137\/s0097539796305365","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"864-889","source":"Crossref","is-referenced-by-count":32,"title":["Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design"],"prefix":"10.1137","volume":"28","author":[{"given":"Giuseppe","family":"Liotta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187749"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, M. Hansen, and T. Leighton,\n                      Solving query\u2010retrieval problems by compacting Voronoi diagrams\n                      , in Proc. 22nd Annu. ACM Sympos. Theory Comput., 1990, Association for Computing Machinery, New York, pp. 331\u2013340.","DOI":"10.1145\/100216.100260"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522822"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/234782.234792"},{"key":"R6","unstructured":"J. E. Baker, I. F. Cruz, G. Liotta, and R. Tamassia,\n                      Animating geometric algorithms over the Web\n                      , in Proc. 12th Annu. ACM Sympos. Comput. Geom., Association for Computing Machinery, New York, 1996, pp. C3\u2013C4."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8702-0"},{"key":"R9","unstructured":"C. Burnikel,\n                      Exact Computation of Voronoi Diagrams and Line Segment Intersections\n                      . Ph.D thesis, Universit\u00e4t des Saarlandes, Mar. 1996."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"C. Burnikel, J. K\u00f6nnemann, K. Mehlhorn, S. N\u00e4her, S. Schirra, and C. Uhrig,\n                      Exact geometric computation in LEDA\n                      , in Proc. 11th Annu. ACM Sympos. Comput. Geom., Association for Computing Machinery, New York, 1995, pp. C18\u2013C19.","DOI":"10.1145\/220279.220330"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra, How to compute the Voronoi\u02d8 diagram of line segments: theoretical and experimental results, Lecture Notes in Comput. Sci., Vol. 855, Springer, Berlin, 1994, 227\u20132391328851","DOI":"10.1007\/BFb0049411"},{"key":"R12","unstructured":"Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra, On degeneracy in geometric computations, ACM, New York, 1994, 16\u20132395d:68145"},{"key":"R13","unstructured":"C. Burnikel, R. Fleischer, K. Mehlhorn, S. Schirra, A strong and easily computable separation bound for arithmetic expressions involving square roots, ACM, New York, 1997, 702\u20137091447719"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80045-0"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80030-4"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009474"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840441"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson,\n                      Safe and effective determinant evaluation\n                      , in Proc. 33rd Ann. IEEE Sympos. Found. Comput. Sci., IEEE Press, Piscataway, NJ, 1992, pp. 387\u2013395.","DOI":"10.1109\/SFCS.1992.267751"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(92)90044-P"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/5.163408"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90120-7"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553877"},{"key":"R24","first-page":"6","volume":"3","author":"Edahiro M.","year":"1984","journal-title":"ACM Trans. Graph."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90107-3"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"S. Fortune,\n                      Stable maintenance of point set triangulations in two dimensions\n                      , in Proc. 30th Ann. IEEE Sympos. Found. Comput. Sci., IEEE Press, Piscataway, NJ, 1989, pp. 494\u2013505.","DOI":"10.1109\/SFCS.1989.63524"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000118"},{"key":"R30","unstructured":"S. Fortune,\n                      Polyhedral modeling with multiprecision integer arithmetic\n                      , Comput. Aided Design, to appear."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"S. Fortune and C. J. Van Wyk,\n                      Efficient exact arithmetic for computational geometry\n                      , in Proc. 9th Annu. ACM Sympos. Comput. Geom., Association for Computing Machinery, New York, 1993, pp. 163\u2013172.","DOI":"10.1145\/160985.161015"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1145\/231731.231735"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"D. H. Greene and F. F. Yao,\n                      Finite\u2010resolution computational geometry\n                      , in Proc. 27th Ann. IEEE Sympos. Found. Comput. Sci., IEEE Press, Piscataway, NJ, 1986, pp. 143\u2013152.","DOI":"10.1109\/SFCS.1986.19"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758770"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"L. J. Guibas, D. Salesin, and J. Stolfi,\n                      Epsilon geometry: Building robust algorithms from imprecise computations\n                      , in Proc. 5th Ann. ACM Sympos. Comput. Geom., Association for Computing Machinery, New York, 1989, pp. 208\u2013217.","DOI":"10.1145\/73833.73857"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/282918.282923"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1109\/2.16223"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1109\/38.41469"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(91)90038-D"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/99902.99905"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675946"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/0206043"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"G. Liotta, F. P. Preparata, and R. Tamassia,\n                      Robust Proximity Queries in Implicit Voronoi Diagrams\n                      , Technical Report CS\u201096\u201016, Center for Geometric Computing, Comput. Sci. Dept., Brown Univ., Providence, RI, 1996.","DOI":"10.21236\/ADA313538"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, S. N\u00e4her, T. Schilz, S. Schirra, M. Seel, R. Seidel, and C. Uhrig,\n                      Checking geometric programs or verification of geometric structures\n                      , in Proc. 12th Ann. ACM Sympos. Comput. Geom., Association for Computing Machinery, New York, 1996, pp. 159\u2013165.","DOI":"10.1145\/237218.237344"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90061-6"},{"key":"R49","unstructured":"E. M\u00fccke,\n                      Detri 2.2: A robust implementation for 3d Triangulations\n                      , manuscript, http:\/\/www.geom.umn.edu:80\/software\/cglist\/lowdvod.html (1996)."},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1137\/0221020"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"R54","first-page":"1471","volume":"80","author":"Sugihara K.","year":"1992","journal-title":"Proc. IEEE, IEEE Press, Piscataway, NJ"},{"key":"R55","unstructured":"K. Sugihara, Y. Ooishi, and T. Imai,\n                      Topology\u2010oriented approach to robustness and its applications to several Voronoi\u2010diagram algorithms\n                      , in Proc. 2nd Canad. Conf. Comput. Geom., 1990, pp. 36\u201339."},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900009"},{"key":"R57","unstructured":"C. Yap and T. Dub\u00e9,\n                      A Basis for Implementing Exact Geometric Algorithms\n                      , manuscript, http:\/\/simulation.nyu.edu\/projects\/exact\/references.html (1993)."},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80069-7"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00040-2"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796305365","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:03Z","timestamp":1787336043000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796305365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539796305365"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796305365","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}