{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T13:52:16Z","timestamp":1784641936434,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":114,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540638186","type":"print"},{"value":"9783540696537","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63818-0_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:35:54Z","timestamp":1330281354000},"page":"255-287","source":"Crossref","is-referenced-by-count":7,"title":["Precision and robustness in geometric computations"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Schirra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"9_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"9_CR2","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":"9_CR3","unstructured":"F. Avnaim. C++GAL: A C++ Library for Geometric Algorithms, 1994."},{"key":"9_CR4","unstructured":"F. Avnaim, J.D. Boissonnat, O. Devillers, F.P. Preparata, and M. Yvinec. Evaluating signs of determinants using single precision arithmetic. Technical Report 2306, INRIA Sophia-Antipolis, 1994."},{"key":"9_CR5","unstructured":"J.E. Baker, R. Tamassia, and L. Vismara. GeomLib: Algorithm engineering for a geometric computing library, 1997. (Preliminary report)."},{"key":"9_CR6","unstructured":"J.L. Barber. Computational geometry with imprecise data and arithmetic: Phd Thesis. Technical Report CS-TR-377-92, Princeton University, 1992."},{"key":"9_CR7","unstructured":"M.O. Benouamer, P. Jaillon, D. Michelucci, and J-M. Moreau. A \u201clazy\u201d solution to imprecision in computational geometry. In Proc. of the 5th Canad. Conf. on Camp. Geom., pages 73\u201378, 1993."},{"key":"9_CR8","volume-title":"Algorithmic Geometry","author":"J.D. Boissonnat","year":"1997","unstructured":"J.D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, Cambridge, UK, 1997."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann, I.Z. Emiris, V.Y. Pan, and S. Pion. Computing exact geometric predicates using modular arithmetic with single precision. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 174\u2013182, 1997.","DOI":"10.1145\/262839.262948"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann and M. Yvinec. Efficient exact evaluation of signs of determinants. In Proc. 13th Annu. AGM Sympos. Comput. Geom., pages 166\u2013173, 1997.","DOI":"10.1145\/262839.262944"},{"key":"9_CR11","unstructured":"C. Burnikel. Exact Computation of Voronoi Diagrams and Line Segment Intersections. PhD Thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1996."},{"key":"9_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":"9_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 11 th ACM Symposium on Computational Geometry, pages C18\u2013C19, 1995.","DOI":"10.1145\/220279.220330"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"C. Burnikel, K. Mehlhorn, and S. Schirra. How to compute the Voronoi diagram of line segments: Theoretical and experimental results. In ESA94, pages 227\u2013239, 1994.","DOI":"10.1007\/BFb0049411"},{"key":"9_CR15","unstructured":"C. Burnikel, K. Mehlhorn, and S. Schirra. On degeneracy in geometric computations. In Proc. of the 5th ACM-SIAM Symp. on Discrete Algorithms, pages 16\u201323, 1994."},{"key":"9_CR16","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":"9_CR17","unstructured":"J.F. Canny. The Complexity of Robot Motion Planning. PhD Thesis, 1987."},{"key":"9_CR18","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0747-7171(08)80012-0","volume":"9","author":"J.F. Canny","year":"1990","unstructured":"J.F. Canny. Generalised characteristic polynomials. J. Symbolic Computation, 9:241\u2013250, 1990.","journal-title":"J. Symbolic Computation"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Wei Chen, Koichi Wada, and Kimio Kawaguchi. Parallel robust algorithms for constructing strongly convex hulls. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 133\u2013140, 1996.","DOI":"10.1145\/237218.237329"},{"key":"9_CR20","unstructured":"N.R. Chrisman. The accuracy of map overlays: a reassessment. In D.J. Peuquet and D.F. Marble, editors, Introductory Readings in Geographic Information Systems, pages 308\u2013320. Taylor & Francis, London, 1990."},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson. Safe and effective determinant evaluation. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 387\u2013395, 1992.","DOI":"10.1109\/SFCS.1992.267751"},{"key":"9_CR22","unstructured":"J.L.D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics, 1993. Presented at SIBGRAPI'93, Recife (Brazil), October 20\u201322."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry. Springer Verlag, 1997.","DOI":"10.1007\/978-3-662-03427-9"},{"key":"9_CR24","unstructured":"P. de Rezende and W. Jacometti. Geolab: An environment for development of algorithms in computational geometry. In Proc. 5th Canad. Conf. Comput. Geom., pages 175\u2013180, Waterloo, Canada, 1993."},{"key":"9_CR25","doi-asserted-by":"crossref","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":"9_CR26","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/0167-8396(92)90044-P","volume":"9","author":"T.K. Dey","year":"1992","unstructured":"T.K. Dey, K. Sugihara, and C.L. Bajaj. Delaunay triangulations in three dimensions with finite precision arithmetic. Computer Aided Geometric Design, 9:457\u2013470, 1992.","journal-title":"Computer Aided Geometric Design"},{"key":"9_CR27","unstructured":"D. Douglas. It makes me so CROSS. In D.J. Peuquet and D.F. Marble, editors, Introductory Readings in Geographic Information Systems, pages 303\u2013307. Taylor & Francis, London, 1990."},{"key":"9_CR28","unstructured":"T. Dub\u00e9, K. Ouchi, and C.K. Yap. Tutorial for Real\/Expr package. 1996."},{"key":"9_CR29","unstructured":"T. Dub\u00e9 and C.K. Yap. A basis for implementing exact computational geometry. extended abstract, 1993."},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Verlag, 1986.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"9_CR31","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner and E. M\u00fccke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. on Graphics, 9:66\u2013104, 1990.","journal-title":"ACM Trans. on Graphics"},{"key":"9_CR32","doi-asserted-by":"crossref","unstructured":"I. Emiris and J. Canny. A general approach to removing degeneracies. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Sience, pages 405\u2013413, 1991.","DOI":"10.1109\/SFCS.1991.185399"},{"key":"9_CR33","doi-asserted-by":"crossref","unstructured":"I. Emiris and J. Canny. An efficient approach to removing geometric degeneracies. In Proc. of the 8th ACM Symp. on Computational Geometry, pages 74\u201382, 1992.","DOI":"10.1145\/142675.142694"},{"key":"9_CR34","unstructured":"A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Sch\u00f6nherr. The CGAL kernel: a basis for geometric computation. In Ming C. Lin and Dinesh Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering (WACG96), pages 191\u2013202. Springer LNCS 1148, 1996."},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"S. Fang and B. Br\u00fcderlin. Robustness in geometric modeling \u2014 tolerance based methods. In Proc. Workshop on Computational Geometry CG'91, pages 85\u2013102. Springer Verlag LNCS 553, 1991.","DOI":"10.1007\/3-540-54891-2_7"},{"key":"9_CR36","doi-asserted-by":"crossref","unstructured":"A. R. Forrest. Computational geometry in practice. In R. A. Earnshaw, editor, Fundamental Algorithms for Computer Graphics, volume F17 of NATO ASI, pages 707\u2013724. Springer-Verlag, 1985.","DOI":"10.1007\/978-3-642-84574-1_30"},{"key":"9_CR37","doi-asserted-by":"crossref","unstructured":"S. Fortune. Stable maintenance of point-set triangulations in two dimensions. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Sience, pages 494\u2013499, 1989.","DOI":"10.1109\/SFCS.1989.63524"},{"key":"9_CR38","unstructured":"S. Fortune. Progress in computational geometry. In R. Martin, editor, Directions in Geometric Computing, pages 81\u2013128. Information Geometers Ltd., 1993."},{"key":"9_CR39","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1142\/S0218195995000118","volume":"5","author":"S. Fortune","year":"1995","unstructured":"S. Fortune. Numerical stability of algorithms for 2D Delaunay triangulations and Voronoi diagrams. Int. J. Computational Geometry and Applications, 5:193\u2013213, 1995.","journal-title":"Int. J. Computational Geometry and Applications"},{"key":"9_CR40","doi-asserted-by":"crossref","unstructured":"S. Fortune and V. Milenkovic. Numerical stability of algorithms for line arrangements. In Proc. of the 7th ACM Symp. on Computational Geometry, pages 334\u2013341, 1991.","DOI":"10.1145\/109648.109685"},{"key":"9_CR41","doi-asserted-by":"crossref","unstructured":"S. Fortune and C. van Wyk. Efficient exact arithmetic for computational geometry. In Proc. of the 9th ACM Symp. on Computational Geometry, pages 163\u2013172, 1993.","DOI":"10.1145\/160985.161015"},{"key":"9_CR42","unstructured":"S. Fortune and C. van Wyk. LN user manual, 1993."},{"issue":"3","key":"9_CR43","doi-asserted-by":"crossref","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":"9_CR44","first-page":"190","volume":"1","author":"W.R. Franklin","year":"1984","unstructured":"W.R. Franklin. Cartographic errors symptomatic of underlying algebra problems. In Proc. International Symposium on Spatial Data Handling, volume 1, pages 190\u2013208, Z\u00fcrich, 20-24 August 1984.","journal-title":"Proc. International Symposium on Spatial Data Handling"},{"key":"9_CR45","unstructured":"G.-J. Giezeman. PlaGeo, a library for planar geometry, and SpaGeo, a library for spatial geometry, 1994."},{"key":"9_CR46","doi-asserted-by":"crossref","unstructured":"D. Goldberg. What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys, pages 5\u201348, 1991.","DOI":"10.1145\/103162.103163"},{"key":"9_CR47","first-page":"113","volume-title":"Advances in Cartography","author":"M.F. Goodchild","year":"1991","unstructured":"M.F. Goodchild. Issues of quality and uncertainty. In J.C. Muller, editor, Advances in Cartography, pages 113\u2013139. Elsevier Applied Science, London, 1991."},{"key":"9_CR48","doi-asserted-by":"crossref","unstructured":"M. Goodrich, L. Guibas, J. Hershberger, and P. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 284\u2013293, 1997.","DOI":"10.1145\/262839.262985"},{"key":"9_CR49","unstructured":"T. Granlund. GNU MP, The GNU Multiple Precision Arithmetic Library, 2.0.2 edition, June 1996."},{"key":"9_CR50","doi-asserted-by":"crossref","unstructured":"D. Greene and F. Yao. Finite resolution computational geometry. In Proc. of the.27th IEEE Symposium on Foundations of Computer Science, pages 143\u2013152, 1986.","DOI":"10.1109\/SFCS.1986.19"},{"key":"9_CR51","doi-asserted-by":"crossref","unstructured":"L. Guibas and D. Marimont. Rounding arrangements dynamically. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 190\u2013199, 1995.","DOI":"10.1145\/220279.220300"},{"key":"9_CR52","doi-asserted-by":"crossref","unstructured":"L. Guibas, D. Salesin, and J. Stolfi. Epsilon geometry: Building robust algorithms from imprecise computations. In Proc. of the 5th ACM Symp. on Computational Geometry, pages 208\u2013217, 1989.","DOI":"10.1145\/73833.73857"},{"key":"9_CR53","doi-asserted-by":"crossref","unstructured":"L. Guibas, D. Salesin, and J. Stolfi. Constructing strongly convex approximate hulls with inaccurate primitives. In Proc. SIGAL Symp. on Algorithms, pages 261\u2013270, Tokyo, 1990.","DOI":"10.1007\/3-540-52921-7_75"},{"key":"9_CR54","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF01178779","volume":"29","author":"K. Hinrichs","year":"1992","unstructured":"K. Hinrichs, J. Nievergelt, and P. Schorn. An all-round sweep algorithm for 2dimensional nearest-neighbor problems. Acta Informatioa, 29:383\u2013394, 1992.","journal-title":"Acta Informatioa"},{"key":"9_CR55","unstructured":"J.D. Hobby. Practical line segment interscetion with finite precision output. Technical Report 93\/2-27, Bell Laboratories (Lucent Technologies), 1993."},{"key":"9_CR56","doi-asserted-by":"crossref","unstructured":"C.M. Hoffmann. The problem of accuracy and robustness in geometric computation. IEEE Computer, pages 31\u201341, March 1989.","DOI":"10.1109\/2.16223"},{"key":"9_CR57","doi-asserted-by":"crossref","unstructured":"C.M. Hoffmann, J.E. Hopcroft, and M.S. Karasick. Towards implementing robust geometric computations. In Proc. of the 4th ACM Symp. on Computational Geometry, pages 106\u2013117, 1988.","DOI":"10.1145\/73393.73405"},{"key":"9_CR58","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01758769","volume":"7","author":"J.E. Hopcroft","year":"1992","unstructured":"J.E. Hopcroft and P.J. Kahn. A paradigm for robust geometric algorithms. Algorithmica, 7:339\u2013380, 1992.","journal-title":"Algorithmica"},{"key":"9_CR59","doi-asserted-by":"crossref","unstructured":"K. Jensen and N. Wirth. PASCAL-User Manual and Report. Revised for the ISO Pascal Standard. Springer Verlag, 3rd edition, 1985.","DOI":"10.1007\/978-1-4684-0261-2"},{"key":"9_CR60","doi-asserted-by":"crossref","unstructured":"S. Kahan and J. Snoeyink. On the bit complexity of minimum link paths: Superquadratic algorithms for problems solvable in linear time. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 151\u2013158, 1996.","DOI":"10.1145\/237218.237342"},{"issue":"1","key":"9_CR61","doi-asserted-by":"crossref","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":"9_CR62","unstructured":"R. Klein. Algorithmische Geometrie. Addison-Wesley, 1997. (in German)."},{"key":"9_CR63","doi-asserted-by":"crossref","unstructured":"A. Knight, J. May, M. McAffer, T. Nguyen, and J.-R. Sack. A computational geometry workbench. In Proc. 6th Annu. ACM Sympos. Comput. Geom., page 370, 1990.","DOI":"10.1145\/98524.98602"},{"key":"9_CR64","unstructured":"D.E. Knuth. The Art of Computer Programming Vol. 2: Seminumerical Algorithms. Addison-Wesley, 2nd edition, 1981."},{"key":"9_CR65","volume-title":"Axioms and Hulls, volume 606 of Lecture Notes in Computer Science","author":"D. E. Knuth","year":"1992","unstructured":"Donald E. Knuth. Axioms and Hulls, volume 606 of Lecture Notes in Computer Science. Springer-Verlag, Heidelberg, Germany, 1992."},{"key":"9_CR66","volume-title":"Computational geometry and computer graphics in C++","author":"M.J. Laszlo","year":"1996","unstructured":"M.J. Laszlo. Computational geometry and computer graphics in C++. Prentice Hall, Upper Saddle River, NJ, 1996."},{"key":"9_CR67","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01758851","volume":"8","author":"Z. Li","year":"1992","unstructured":"Z. Li and V. Milenkovic. Constructing strongly convex hulls using exact or rounded arithmetic. Algorithmica, 8:345\u2013364, 1992.","journal-title":"Algorithmica"},{"key":"9_CR68","unstructured":"LIDIA-Group, Fachbereich Informatik Institut f\u00fcr Theoretische Informatik TH Darmstadt. LiDlA Manual A library for computational number theory, 1.3 edition, April 1997."},{"key":"9_CR69","doi-asserted-by":"crossref","unstructured":"G. Liotta, F. 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":"9_CR70","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer Verlag, 1984.","DOI":"10.1007\/978-3-642-69900-9"},{"key":"9_CR71","unstructured":"K. Mehlhorn and S. N\u00e4her. Implementation of a sweep line algorithm for the straight line segment intersection problem. Technical Report MPI-I-94-160, Max-Planck-Institut f\u00fcr Informatik, 1994."},{"key":"9_CR72","first-page":"223","volume-title":"13th World Computer Congress IFIP94, volume 1","author":"K. Mehlhorn","year":"1994","unstructured":"K. Mehlhorn and S. N\u00e4her. The implementation of geometric algorithms. In 13th World Computer Congress IFIP94, volume 1, pages 223\u2013231. Elsevier Science B.V. North-Holland, Amsterdam, 1994."},{"key":"9_CR73","doi-asserted-by":"crossref","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":"9_CR74","unstructured":"K. Mehlhorn, S. N\u00e4her, and C. Uhrig. The LEDA User manual, 3.5 edition, 1997. cf.http:\/\/www.mpi-sb.mpg.de\/LEDA\/leda.html."},{"key":"9_CR75","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0196-6774(82)90019-0","volume":"3","author":"M. Mignotte","year":"1982","unstructured":"M. Mignotte. Identification of algebraic numbers. Journal of Algorithms, 3:197\u2013204, 1982.","journal-title":"Journal of Algorithms"},{"key":"9_CR76","doi-asserted-by":"crossref","unstructured":"M. Mignotte. Mathematics for Computer Algebra. Springer Vertag, 1992.","DOI":"10.1007\/978-1-4613-9171-5"},{"key":"9_CR77","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0004-3702(88)90061-6","volume":"37","author":"V. Milenkovic","year":"1988","unstructured":"V. Milenkovic. Verifiable implementations of geometric algorithms using finite precision arithmetic. Artificial Intelligence, 37:377\u2013401, 1988.","journal-title":"Artificial Intelligence"},{"key":"9_CR78","doi-asserted-by":"crossref","unstructured":"V. Milenkovic and L. R. Nackman. Finding compact coordinate representations for polygons and polyhedra. In Proc. 6th Annu. ACM Sympos. Comput. Geom., pages 244\u2013252, 1990.","DOI":"10.1145\/98524.98579"},{"key":"9_CR79","volume-title":"Interval Analysis","author":"R.E. Moore","year":"1966","unstructured":"R.E. Moore. Interval Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1966."},{"key":"9_CR80","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."},{"issue":"2","key":"9_CR81","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/MCG.1984.275931","volume":"4","author":"S.P. Mudur","year":"1984","unstructured":"S.P. Mudur and P.A. Koparkar. Interval methods for processing geometric objects. IEEE Computer Graphics and Applications, 4(2):7\u201317, 1984.","journal-title":"IEEE Computer Graphics and Applications"},{"key":"9_CR82","volume-title":"Computational Geometry: An Introduction through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"K. Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994."},{"key":"9_CR83","volume-title":"Algorithms and Data Structures: with Applications to Graphics and Geometry","author":"J. Nievergelt","year":"1993","unstructured":"J. Nievergelt and K. H. Hinrichs. Algorithms and Data Structures: with Applications to Graphics and Geometry. Prentice Hall, Englewood Cliffs, NJ, 1993."},{"key":"9_CR84","unstructured":"J. Nievergelt and P. Schorn. Das R\u00e4tsel den verzopften Geraden. Informatik Spektrum, (11):163\u2013165, 1988. (in German)."},{"key":"9_CR85","series-title":"Technical Report 163","volume-title":"XYZ: Software for geometric computation","author":"J. Nievergelt","year":"1991","unstructured":"J. Nievergelt, P. Schorn, M. de Lorenzi, C. Ammann, and A. Br\u00fcngger. XYZ: Software for geometric computation. Technical Report 163, Institut f\u00fcr Theorische Informatik, ETH, Z\u00fcrich, Switzerland, 1991."},{"key":"9_CR86","volume-title":"Computational geometry in C","author":"J. O'Rourke","year":"1994","unstructured":"J. O'Rourke. Computational geometry in C. Cambridge University Press, Cambridge, 1994."},{"key":"9_CR87","doi-asserted-by":"crossref","unstructured":"T. Ottmann, G. Thiemt, and C. Ullrich. Numerical stability of geometric algorithms. In Proc. of the 3rd ACM Symp. on Computational Geometry, pages 119\u2013125, 1987.","DOI":"10.1145\/41958.41970"},{"key":"9_CR88","unstructured":"K. Ouchi. Real\/Expr: Implementation of exact computation, 1997."},{"key":"9_CR89","doi-asserted-by":"crossref","unstructured":"M. Overmars. Designing the computational geometry algorithms library CGAL. In Ming C. Lin and Dinesh Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering (WACG96), pages 53\u201358. Springer LNCS 1148, 1996.","DOI":"10.1007\/BFb0014484"},{"key":"9_CR90","first-page":"399","volume":"4","author":"J. Perkal","year":"1956","unstructured":"J. Perkal. On epsilon length. Bulletin de l'Acad\u00e9mie Polonaise des Sciences, 4:399\u2013403, 1956.","journal-title":"Bulletin de l'Acad\u00e9mie Polonaise des Sciences"},{"key":"9_CR91","doi-asserted-by":"crossref","unstructured":"F. Preparata and M.I. Sharnos. Computational Geometry. Springer Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"9_CR92","doi-asserted-by":"crossref","unstructured":"D.M. Priest. Algorithms for arbitrary precision floating point arithmetic. In 10th Symposium on Computer Arithmetic, pages 132\u2013143. IEEE Computer Society Press, 1991.","DOI":"10.1109\/ARITH.1991.145549"},{"key":"9_CR93","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":"9_CR94","unstructured":"D. Pullar. Spatial overlay with inexact numerical data. In Proc. of Auto-Carto 10, pages 313\u2013329, 1991."},{"key":"9_CR95","first-page":"288","volume":"11","author":"D. Pullar","year":"1993","unstructured":"D. Pullar. Consequences of using a tolerance paradigm in spatial overlay. In Proc. of Auto-Carto 11, pages 288\u2013296, 1993.","journal-title":"Proc. of Auto-Carto"},{"key":"9_CR96","unstructured":"P. Schorn. An object-oriented workbench for experimental geometric computation. In Proc. 2nd Canad. Conf. Comput. Geom., pages 172\u2013175, 1990."},{"key":"9_CR97","unstructured":"P. Schorn. Robust Algorithms in a Program Library for Geometric Algorithms. PhD Thesis, Informatik-Dissertationen ETH Z\u00fcrich, 1991."},{"key":"9_CR98","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1006\/jsco.1993.1039","volume":"16","author":"P. Schorn","year":"1993","unstructured":"P. Schorn. An axiomatic approach to robust geometric programs. J. Symbolic Computation, 16:155\u2013165, 1993.","journal-title":"J. Symbolic Computation"},{"issue":"1","key":"9_CR99","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1093\/comjnl\/37.1.35","volume":"37","author":"P. Schorn","year":"1994","unstructured":"P. Schorn. Degeneracy in geometric computation and the perturbation approach. The Computer Journal, 37(1):35\u201342, 1994.","journal-title":"The Computer Journal"},{"key":"9_CR100","doi-asserted-by":"crossref","unstructured":"R. Seidel. The nature and meaning of perturbations in geometric computations. In STACS94, 1994.","DOI":"10.1007\/3-540-57785-8_127"},{"key":"9_CR101","unstructured":"B. Serpette, J. Vuillemin, and J.C. Herv\u00e9. BigNum, a portable and efficient package for arbitrary-precision arithmetic. Technical Report 2, Digital Paris Research Laboratory, 1989."},{"key":"9_CR102","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":"9_CR103","unstructured":"J. R. Shewchuk. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator. In Ming C. Lin and Dinesh Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering (WACG96), pages 203\u2013222, 1996."},{"key":"9_CR104","first-page":"9","volume":"22","author":"IEEE Standard","year":"1987","unstructured":"IEEE Standard. 754-1985 for binary floating-point arithmetic. SIGPLAN, 22:9\u201325, 1987.","journal-title":"SIGPLAN"},{"issue":"3","key":"9_CR105","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/0097-8493(91)90002-Y","volume":"15","author":"K.G. Suffern","year":"1991","unstructured":"K.G. Suffern and E.D. Fackerell. Interval methods in computer graphics. Computers & Graphics, 15(3):331\u2013340, 1991.","journal-title":"Computers & Graphics"},{"key":"9_CR106","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0022-0000(89)90046-9","volume":"39","author":"K. Sugihara","year":"1989","unstructured":"K. Sugihara. On finite-precision representations of geometric objects. J. Comput. Syst. Sci., 39:236\u2013247, 1989.","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9_CR107","first-page":"468","volume":"E75-A","author":"K. Sugihara","year":"1992","unstructured":"K. Sugihara. A simple method for avoiding numerical errors and degeneracies in Voronoi diagram construction. IEICE Trans. Fundamentals, E75-A(4):468\u2013477, 1992.","journal-title":"IEICE Trans. Fundamentals"},{"key":"9_CR108","unstructured":"K. Sugihara and M. Iri. Construction of the Voronoi diagram for over 105 generators in single-precision arithmetic. In Abstracts 1st Canad. Conf. Comput. Geom., page 42, 1989."},{"issue":"4","key":"9_CR109","first-page":"380","volume":"12","author":"K. Sugihara","year":"1989","unstructured":"K. Sugihara and M. Iri. A solid modelling system free from topological inconsistency. Journal of Information Processing, 12(4):380\u2013393, 1989.","journal-title":"Journal of Information Processing"},{"key":"9_CR110","unstructured":"C. K. Yap. Robust geometric computation. In J. E. Goodman and J. O'Rourke, editors, CRC Handbook in Computational Geometry. CRC Press. (to appear)."},{"key":"9_CR111","doi-asserted-by":"crossref","unstructured":"C. K. Yap and T. Dub\u00e9. The exact computation paradigm. In D.Z. Du and F. Hwang, editors, Computing in Euclidean Geometry, pages 452\u2013492. World Scientific Press, 1995. 2nd edition.","DOI":"10.1142\/9789812831699_0011"},{"key":"9_CR112","doi-asserted-by":"crossref","unstructured":"C.K. Yap. A geometric consistency theorem for a symbolic perturbation scheme. In Proc. of the 4th ACM Symp. on Computational Geometry, pages 134\u2013141, 1988.","DOI":"10.1145\/73393.73407"},{"key":"9_CR113","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0747-7171(08)80069-7","volume":"10","author":"C.K. Yap","year":"1990","unstructured":"C.K. Yap. Symbolic treatment of geometric degeneracies. J. Symbolic Comput., 10:349\u2013370, 1990.","journal-title":"J. Symbolic Comput."},{"issue":"1-2","key":"9_CR114","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0925-7721(95)00040-2","volume":"7","author":"C.K. Yap","year":"1997","unstructured":"C.K. Yap. Towards exact geometric computation. Computational Geometry: Theory and Applications, 7(1-2):3\u201323, 1997. Preliminary version appeared in Proc. of the 5th Canad. Conf. on Comp. Geom., pages 405\u2013419, (1993).","journal-title":"Computational Geometry: Theory and Applications"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Foundations of Geographic Information Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63818-0_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:19:45Z","timestamp":1605629985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63818-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638186","9783540696537"],"references-count":114,"URL":"https:\/\/doi.org\/10.1007\/3-540-63818-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}