{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T08:12:57Z","timestamp":1773648777160,"version":"3.50.1"},"reference-count":152,"publisher":"Elsevier","isbn-type":[{"value":"9780444825377","type":"print"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1016\/b978-044482537-7\/50015-2","type":"book-chapter","created":{"date-parts":[[2007,9,8]],"date-time":"2007-09-08T07:17:56Z","timestamp":1189235876000},"page":"597-632","source":"Crossref","is-referenced-by-count":21,"title":["Robustness and Precision Issues in Geometric Computation**Work on this survey was partially supported by the ESPRIT IV Long Term Research Project No. 21957 (CGAL)."],"prefix":"10.1016","author":[{"given":"Stefan","family":"Schirra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/B978-044482537-7\/50015-2_bb0010","series-title":"Applicable and robust geometric computing","author":"Agarwal","year":"1995"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0015","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0020","series-title":"Introduction to Interval Computation","author":"Alefeld","year":"1983"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0025","series-title":"C++ GAL: A C++ Library for Geometric Algorithms","author":"Avnaim","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0030","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02522822","article-title":"Evaluating signs of determinants using single-precision arithmetic","volume":"17","author":"Avnaim","year":"1997","journal-title":"Algorithmica"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0035","series-title":"Robust decompositions of polyhedra","first-page":"267","volume":"405","author":"Bajaj","year":"1989"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0040","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1137\/0221025","article-title":"Convex decomposition of polyhedra and robustness","volume":"21","author":"Bajaj","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0045","series-title":"GeomLib: Algorithm engineering for a geometric computing library","author":"Baker","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0050","series-title":"Computational geometry with imprecise data and arithmetic","author":"Barber","year":"1992"},{"issue":"4","key":"10.1016\/B978-044482537-7\/50015-2_bb0055","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The Quickhull algorithm for convex hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0060","first-page":"479","article-title":"A robust algorithm for point in polyhedron","author":"Barber","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0065","first-page":"73","article-title":"A lazy solution to imprecision in computational geometry","author":"Benouamer","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0070","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","article-title":"Algorithms for reporting and counting geometric intersections","volume":"C-28","author":"Bentley","year":"1979","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0075","first-page":"670","article-title":"Computing sums of radicals in polynomial time","author":"Bl\u00f6mer","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0080","series-title":"Robust plane sweep for intersecting segments","author":"Boissonnat","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0085","series-title":"Algorithmic Geometry","author":"Boissonnat","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0090","first-page":"174","article-title":"Computing exact geometric predicates using modular arithmetic with single precision","author":"Br\u00f6nnimann","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0095","first-page":"166","article-title":"Efficient exact evaluation of signs of determinants","author":"Br\u00f6nnimann","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0100","series-title":"Exact computation of Vorono, diagrams and line segment intersections","author":"Burnikel","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_rf0105","first-page":"702","article-title":"A strong and easily computable separation bound for arithmetic expressions involving square roots","author":"Burnikel","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0110","series-title":"How to compute the Vorono, diagram of line segments: Theoretical and experimental results","first-page":"227","author":"Burnikel","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0115","first-page":"16","article-title":"On degeneracy in geometric computations","author":"Burnikel","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0120","article-title":"The LEDA class real number","author":"Burnikel","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0125","series-title":"ACM Doctoral Dissertation Award 1987","article-title":"The Complexity of Robot Motion Planning","author":"Canny","year":"1987"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0130","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0747-7171(08)80012-0","article-title":"Generalised characteristic polynomials","volume":"9","author":"Canny","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0135","unstructured":"CGAL project. See http:\/\/www.cs.uu.nl\/CGAL\/"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0140","first-page":"67","article-title":"An experiment using LN for exact geometric computations","author":"Chang","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0145","first-page":"133","article-title":"Parallel robust algorithms for constructing strongly convex hulls","author":"Chen","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0150","first-page":"387","article-title":"Safe and effective determinant evaluation","author":"Clarkson","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0155","series-title":"Affine arithmetic and its applications to computer graphics","article-title":"1993","author":"Comba","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0160","series-title":"Computational Geometry","author":"de Berg","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0165","series-title":"Geolab: An environment for development of algorithms in computational geometry","first-page":"175","author":"de Rezende","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0170","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/BF01397083","article-title":"A floating-point technique for extending the available precision","volume":"18","author":"Dekker","year":"1971","journal-title":"Numer. Math."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0175","article-title":"A probabilistic analysis of the power of arithmetic filters","author":"Devillers","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0180","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/0167-8396(92)90044-P","article-title":"Delaunay triangulations in three dimensions with finite precision arithmetic","volume":"9","author":"Dey","year":"1992","journal-title":"Comput. Aided Geom. Design"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0185","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/0022-0000(90)90019-H","article-title":"Applied computational geometry: Towards robust solutions of basic problems","volume":"40","author":"Dobkin","year":"1989","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0190","series-title":"Introductory Readings in Geographic Information Systems","first-page":"303","article-title":"It makes me so CROSS","author":"Douglas","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0195","series-title":"Tutorial for Real\/Expr Package","author":"Dub\u00e9","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0200","series-title":"A basis for implementing exact computational geometry","author":"Dub\u00e9","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0205","series-title":"Algorithms in Combinatorial Geometry","author":"Edelsbrunner","year":"1986"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0210","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/77635.77639","article-title":"Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms","volume":"9","author":"Edelsbrunner","year":"1990","journal-title":"ACM Trans, on Graphics"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0215","article-title":"A complete implementation for computing general dimensional convex hulls","author":"Emiris","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0220","first-page":"74","article-title":"An efficient approach to removing geometric degeneracies","author":"Emiris","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0225","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1137\/S0097539792235918","article-title":"A general approach to removing degeneracies","volume":"24","author":"Emiris","year":"1995","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"10.1016\/B978-044482537-7\/50015-2_bb0230","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/PL00014417","article-title":"Efficient perturbations for handling geometric degeneracies","volume":"19","author":"Emiris","year":"1997","journal-title":"Algorithmica"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0235","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/BF01187021","article-title":"A workbench for computational geometry","volume":"11","author":"Epstein","year":"1994","journal-title":"Algorithmica"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0240","series-title":"Applied Computational Geometry: Towards Geometric Engineering (WACG96)","first-page":"191","article-title":"The CGAL kernel : A basis for geometric computation","author":"Fabri","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_rf0240","first-page":"85","article-title":"Robustness in geometric modeling \u2014 tolerance-based methods","volume":"553","author":"Fang","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0250","first-page":"707","article-title":"Computational geometry in practice","volume":"F17","author":"Forrest","year":"1985"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0255","series-title":"Techniques for Computer Graphics","article-title":"Computational geometry and software engineering: Towards a geometric computing environment","author":"Forrest","year":"1987"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0260","first-page":"494","article-title":"Stable maintenance of point set triangulations in two dimensions","author":"Fortune","year":"1989"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0265","series-title":"Directions in Geometric Computing","first-page":"81","article-title":"Progress in computational geometry","author":"Fortune","year":"1993"},{"issue":"1","key":"10.1016\/B978-044482537-7\/50015-2_bb0270","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1142\/S0218195995000118","article-title":"Numerical stability of algorithms for 2-d Delaunay triangulations","volume":"5","author":"Fortune","year":"1995","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0275","first-page":"9","article-title":"Robustness issues in geometric algorithms","volume":"1148","author":"Fortune","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0280","first-page":"334","article-title":"Numerical stability of algorithms for line arrangements","author":"Fortune","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0285","series-title":"LN user manual","author":"Fortune","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0290","first-page":"163","article-title":"Efficient exact arithmetic for computational geometry","author":"Fortune","year":"1993"},{"issue":"3","key":"10.1016\/B978-044482537-7\/50015-2_bb0295","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1145\/231731.231735","article-title":"Static analysis yields efficient exact integer arithmetic for computational geometry","volume":"15","author":"Fortune","year":"1996","journal-title":"ACM Trans. Graph."},{"issue":"2","key":"10.1016\/B978-044482537-7\/50015-2_bb0300","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1142\/S0218195994000100","article-title":"A convex hull algorithm for points with approximately known positions","volume":"4","author":"Franciosa","year":"1994","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0305","first-page":"190","article-title":"Cartographic errors symptomatic of underlying algebra problems","volume":"1","author":"Franklin","year":"1984","journal-title":"Proc. Internat. Sympos. Spatial Data Handling"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0310","series-title":"PlaGeo, a Libran\u00b7for Planar Geometry and SpaGeo, a Library for Spatial Geometry","author":"Giezeman","year":"1994"},{"issue":"1","key":"10.1016\/B978-044482537-7\/50015-2_bb0315","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/103162.103163","article-title":"What every computer scientist should know about floating-point arithmetic","volume":"32","author":"Goldberg","year":"1991","journal-title":"ACM Comput. Surv."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0320","series-title":"Advances in Cartography","first-page":"113","article-title":"Issues of quality and uncertainty","author":"Goodchild","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0325","first-page":"284","article-title":"Snap rounding line segments efficiently in two and three dimensions","author":"Goodrich","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0330","series-title":"GNU MP, The GNU Multiple Precision Arithmetic Library","author":"Granlund","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0335","first-page":"143","article-title":"Finite-resolution computational geometry","author":"Greene","year":"1986"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0340","first-page":"15","article-title":"Implementing geometric algorithms robustly","volume":"1148","author":"Guibas","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0345","first-page":"190","article-title":"Rounding arrangements dynamically","author":"Guibas","year":"1995"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0350","first-page":"208","article-title":"Epsilon geometry: Building robust algorithms from imprecise computations","author":"Guibas","year":"1989"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0355","first-page":"261","article-title":"Constructing strongly convex approximate hulls with inaccurate primitives","volume":"450","author":"Guibas","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0360","first-page":"183","article-title":"4 perturbation scheme for spherical arrangements with application to molecular modeling","author":"Halperin","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0365","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF01178779","article-title":"An all-round sweep algorithm for 2-dimensional nearest-neighbor problems","volume":"29","author":"Hinrichs","year":"1992","journal-title":"Acta Inform\u00e1tica"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0370","series-title":"Practical line segment interscetion with finite precision output","author":"Hobby","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_rf0370","first-page":"106","article-title":"Towards implementing robust geometric computations","author":"Hoffmann","year":"1988"},{"issue":"6","key":"10.1016\/B978-044482537-7\/50015-2_bb0380","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1109\/38.41469","article-title":"Robust set operations on polyhedral solids","volume":"9","author":"Hoffmann","year":"1989","journal-title":"IEEE Comput. Graph. Appl."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0385","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/2.16223","article-title":"The problem of accuracy and robustness in geometric computation","author":"Hoffmann","year":"1989","journal-title":"IEEE Computer"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0390","doi-asserted-by":"crossref","first-page":"339380","DOI":"10.1007\/BF01758769","article-title":"A paradigm for robust geometric algorithms","volume":"7","author":"Hopcroft","year":"1992","journal-title":"Algorithmica"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0395","first-page":"171","article-title":"Numerically robust algorithm for constructing constrained Delaunay triangulation","author":"Inagak","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0400","first-page":"334","article-title":"Numerically robust incremental algorithm for constructing threedimensional Vorono, diagrams","author":"Inagaki","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0405","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0925-7721(94)00017-4","article-title":"Computing convex hull in a floating point arithmetic","volume":"4","author":"Jaromczyk","year":"1994","journal-title":"Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0410","series-title":"PASCAL-User Manual and Report. Revised for the ISO Pascal Standard","author":"Jensen","year":"1985"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0415","first-page":"151","article-title":"On the bit complexity of minimum link paths: Superquadratic algorithms for problems solvable in linear time","author":"Kahan","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0420","series-title":"On the representation and manipulation of rigid solids","author":"Karasick","year":"1989"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0425","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/99902.99905","article-title":"Efficient Delaunay triangulations using rational arithmetic","volume":"10","author":"Karasick","year":"1991","journal-title":"ACM Trans. Graph."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0430","series-title":"Algorithmische Geometrie","author":"Klein","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0435","article-title":"The Art of Computer Programming","volume":"2","author":"Knuth","year":"1981"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0440","article-title":"Axioms and Hulls","volume":"606","author":"Knuth","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0445","series-title":"Computational Geometry and Computer Graphics in C++","author":"Laszlo","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0450","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01758851","article-title":"Constructing strongly convex hulls using exact or rounded arithmetic","volume":"8","author":"Li","year":"1992","journal-title":"Algorithmica"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0455","series-title":"LiDIA Manual A library for computational number theory","article-title":"Fachbereich Informatik Institut f\u00fcr Theoretische Informatik TH Darmstadt","author":"LiDIA-Group","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0460","first-page":"156","article-title":"Robust proximity queries: An illustration of degree-driven algorithm design","author":"Liotta","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0465","series-title":"Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0470","article-title":"Implementation of a sweep line algorithm for the straight tine segment intersection problem","author":"Mehlhom","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0475","first-page":"223","article-title":"The implementation of geometric algorithms","volume":"1","author":"Mehlhom","year":"1994","journal-title":"Proc. 13th World Computer Congress IFIP94"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0480","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/204865.204889","article-title":"LEDA, a platform for combinatorial and geometric computing","volume":"38","author":"Mehlhom","year":"1995","journal-title":"Comm. ACM"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0485","series-title":"The LEDA User manual","author":"Mehlhom","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0490","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0196-6774(82)90019-0","article-title":"Identification of algebraic numbers","volume":"3","author":"Mignotte","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0495","series-title":"Mathematics for Computer Algebra","author":"Mignotte","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0500","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0004-3702(88)90061-6","article-title":"Verifiable implementations of geometric algorithms using finite precision arithmetic","volume":"37","author":"Milenkovic","year":"1988","journal-title":"Artif. Intell."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0505","first-page":"500","article-title":"Double precision geometry: A general technique for calculating line and segment intersections using rounded arithmetic","author":"Milenkovic","year":"1989"},{"issue":"9","key":"10.1016\/B978-044482537-7\/50015-2_bb0510","doi-asserted-by":"crossref","DOI":"10.1016\/0010-4485(93)90071-U","article-title":"Robust polygon modeling","volume":"25","author":"Milenkovic","year":"1993","journal-title":"Comput. Aided Design"},{"key":"10.1016\/B978-044482537-7\/50015-2_rf0510","first-page":"244","article-title":"Finding compact coordinate representations for polygons and polyhedra","author":"Milenkovic","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0520","series-title":"Topology oriented vs. exact arithmetic - experience in implementing the three-dimensional convex hull algorithm","author":"Minakawa","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0525","series-title":"Interval Analysis","author":"Moore","year":"1966"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0530","series-title":"Methods and Applications of Interval Analysis","author":"Moore","year":"1979"},{"issue":"2","key":"10.1016\/B978-044482537-7\/50015-2_bb0535","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/MCG.1984.275931","article-title":"Interval methods for processing geometric objects","volume":"4","author":"Mudur","year":"1984","journal-title":"IEEE Comput. Graph. Appl."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0540","series-title":"Computational Geometry: An Introduction through Randomized Algorithms","author":"Mulmuley","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0545","series-title":"Algorithms and Data Structures: With Applications to Graphics and Geometry","author":"Nievergelt","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0550","first-page":"163","article-title":"Das R\u00e4tsel der verzopften Geraden","volume":"11","author":"Nievergelt","year":"1988","journal-title":"Informatik Spektrum"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0555","article-title":"XYZ: Software for geometric computation","author":"Nievergelt","year":"1991"},{"issue":"4","key":"10.1016\/B978-044482537-7\/50015-2_bb0560","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1006\/gmip.1995.1027","article-title":"Topology oriented divide and conquer algorithm for Vorono, diagrams","volume":"57","author":"Oish","year":"1995","journal-title":"Graph. Models Image Process."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0565","series-title":"Computational Geometry in C","author":"O\u2019Rourke","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0570","first-page":"119","article-title":"Numerical stability of geometric algorithms","author":"Ottmann","year":"1987"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0575","series-title":"Real\/Expr: Implementation of exact computation","author":"Ouchi","year":"1997"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0580","series-title":"Applied Computational Geometry: Towards Geometric Engineering (WACG96)","first-page":"53","article-title":"Designing the computational geometry algorithms library CGAL","author":"Overmars","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0585","first-page":"23","article-title":"Robustness in geometric algorithms","volume":"1148","author":"Preparata","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0590","series-title":"Computational Geometry","author":"Preparata","year":"1985"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0595","first-page":"132","article-title":"Algorithms for arbitrary precision floating point arithmetic","author":"Priest","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0600","series-title":"On properties of floating-point arithmetic: Numerical stability and the cost of accurate computations","author":"Priest","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0605","first-page":"288","article-title":"Consequences of using a tolerance paradigm in spatial overlay","volume":"11","author":"Pullar","year":"1993","journal-title":"Proc. of Auto-Carto"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0610","first-page":"172","article-title":"An object-oriented workbench for experimental geometric computation","author":"Schorn","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0615","article-title":"Robust Algorithms in a Program Library for Geometric Computation","volume":"32","author":"Schorn","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0620","doi-asserted-by":"crossref","first-page":"155165","DOI":"10.1006\/jsco.1993.1039","article-title":"An axiomatic approach to robust geometric programs","volume":"16","author":"Schorn","year":"1993","journal-title":"J. Symbolic Comput."},{"issue":"1","key":"10.1016\/B978-044482537-7\/50015-2_bb0625","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1093\/comjnl\/37.1.35","article-title":"Degeneracy in geometric computation and the perturbation approach","volume":"37","author":"Schom","year":"1994","journal-title":"Comput. J."},{"issue":"4","key":"10.1016\/B978-044482537-7\/50015-2_bb0630","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/97880.97891","article-title":"Using tolerances to guarantee valid polyhedral modeling results","volume":"24","author":"Segal","year":"1990","journal-title":"Comput. Graph."},{"issue":"1","key":"10.1016\/B978-044482537-7\/50015-2_bb0635","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/38.490","article-title":"Partitioning polyhedral objects into nonintersecting parts","volume":"8","author":"Segal","year":"1988","journal-title":"IEEE Comput. Graph. Appl."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0640","first-page":"29","article-title":"Consistent calculations for solids modelling","author":"Segal","year":"1985"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0645","series-title":"The nature and meaning of perturbations in geometric computations","author":"Seidel","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0650","article-title":"BigNum, a portable and efficient package for arbitrary-precision arithmetic","author":"Serpette","year":"1989"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0655","article-title":"Adaptive precision floating-point arithmetic and fast robust geometric predicates","author":"Shewchuk","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_rf0655","first-page":"141","article-title":"Robust adaptive floating-point geometric predicates","author":"Shewchuk","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0665","series-title":"Applied Computational Geometry: Towards Geometric Engineering (WACG96)","first-page":"203","article-title":"Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator","author":"Shewchuk","year":"1996"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0670","first-page":"9","article-title":"754-1985for binary floating-point arithmetic","volume":"22","author":"Standard","year":"1987","journal-title":"SIGPLAN"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0675","first-page":"179","article-title":"Robust point location in approximate polygons","author":"Stewart","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0680","article-title":"The theory and practice of robust geometric computation, or, how to build robust solid modelers","author":"Stewart","year":"1991"},{"issue":"1","key":"10.1016\/B978-044482537-7\/50015-2_bb0685","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1142\/S0218195994000070","article-title":"Local robustness and its application to polyhedral intersection","volume":"4","author":"Stewart","year":"1994","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"3","key":"10.1016\/B978-044482537-7\/50015-2_bb0690","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/0097-8493(91)90002-Y","article-title":"Interval methods in computer graphics","volume":"15","author":"Suffern","year":"1991","journal-title":"Comput. Graphics"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0695","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0022-0000(89)90046-9","article-title":"On flnite-precision representations of geometric objects","volume":"39","author":"Sugihara","year":"1989","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0700","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1109\/38.124289","article-title":"An intersection algorithm based on Delaunay triangulation","volume":"12","author":"Sugihara","year":"1992","journal-title":"IEEE Comput. Graph. Appl."},{"issue":"4","key":"10.1016\/B978-044482537-7\/50015-2_bb0705","first-page":"468","article-title":"A simple method for avoiding numerical errors and degeneracy in Vorono, diagram construction","volume":"E75-A","author":"Sugihara","year":"1992","journal-title":"IEICE Trans. Fundamentals"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0710","first-page":"209","article-title":"Topologically consistent algorithms related to convex polyhedra","volume":"650","author":"Sugihara","year":"1992"},{"issue":"3","key":"10.1016\/B978-044482537-7\/50015-2_bb0715","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1111\/1467-8659.1330045","article-title":"A robust and consistent algorithm for intersecting convex polyhedra","volume":"13","author":"Sugihara","year":"1994","journal-title":"Comput. Graph. Forum"},{"issue":"4","key":"10.1016\/B978-044482537-7\/50015-2_bb0720","first-page":"380","article-title":"A solid modelling system free from topological inconsistency","volume":"12","author":"Sugihara","year":"1989","journal-title":"J. Inform. Process."},{"issue":"9","key":"10.1016\/B978-044482537-7\/50015-2_bb0725","doi-asserted-by":"crossref","first-page":"1471","DOI":"10.1109\/5.163412","article-title":"Construction of the Vorono, diagram for \u2018one million\u2019 generators in singleprecision arithmetic","volume":"80","author":"Sugihara","year":"1992","journal-title":"Proc. IEEE"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0730","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1142\/S0218195994000124","article-title":"A robust topology-oriented incremental algorithm for Vorono, diagrams","volume":"4","author":"Sugihara","year":"1994","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0735","first-page":"36","article-title":"Topology-oriented approach to robustness and its applications to several Voronoi-diagram algorithms","author":"Sugihara","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0740","first-page":"134","article-title":"A geometric consistency theorem for a symbolic perturbation scheme","author":"Yap","year":"1988"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0745","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0747-7171(08)80069-7","article-title":"Symbolic treatment of geometric degeneracies","volume":"10","author":"Yap","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0750","series-title":"CRC Handbook of Discrete and Computational Geometry","first-page":"653","article-title":"Robust geometric computation","author":"Yap","year":"1997"},{"issue":"1-2","key":"10.1016\/B978-044482537-7\/50015-2_rf0750","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0925-7721(95)00040-2","article-title":"Towards exact geometric computation","volume":"7","author":"Yap","year":"1997","journal-title":"Comput. Geom"},{"key":"10.1016\/B978-044482537-7\/50015-2_rf0755","first-page":"405","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50015-2_bb0760","series-title":"Computing in Euclidean Geometry\u2019","first-page":"452","article-title":"The exact computation paradigm","volume":"1","author":"Yap","year":"1995"}],"container-title":["Handbook of Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9780444825377500152?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9780444825377500152?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T02:57:27Z","timestamp":1546570647000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/B9780444825377500152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9780444825377"],"references-count":152,"URL":"https:\/\/doi.org\/10.1016\/b978-044482537-7\/50015-2","relation":{},"subject":[],"published":{"date-parts":[[2000]]}}}