{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:01:02Z","timestamp":1725516062392},"publisher-location":"Berlin, Heidelberg","reference-count":61,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540855200"},{"type":"electronic","value":"9783540855217"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85521-7_8","type":"book-chapter","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T02:45:26Z","timestamp":1217904326000},"page":"127-148","source":"Crossref","is-referenced-by-count":0,"title":["Robustness and Randomness"],"prefix":"10.1007","author":[{"given":"Dominique","family":"Michelucci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean Michel","family":"Moreau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebti","family":"Foufou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/103162.103163","volume":"23","author":"D. Goldberg","year":"1991","unstructured":"Goldberg, D.: What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys\u00a023, 5\u201348 (1991)","journal-title":"ACM Computing Surveys"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithmic Foundations of Geographic Information Systems","author":"S. Schirra","year":"1997","unstructured":"Schirra, S.: Precision and robustness in geometric computations. In: van Kreveld, M., Nievergelt, J., Roos, T., Widmayer, P. (eds.) CISM School 1996. LNCS, vol.\u00a01340, Springer, Heidelberg (1997)"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1115\/1.1375815","volume":"1","author":"C.M. Hoffmann","year":"2001","unstructured":"Hoffmann, C.M.: Robustness in geometric computations. Journal of Computing and Information Science in Engineering\u00a01, 143\u2013156 (2001)","journal-title":"Journal of Computing and Information Science in Engineering"},{"key":"8_CR4","first-page":"927","volume-title":"Handbook of Discrete and Computational Geometry","author":"C. Yap","year":"2004","unstructured":"Yap, C.: Robust geometric computation. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 927\u2013952. CRC Press, Boca Raton (2004)"},{"key":"8_CR5","unstructured":"Keyser, J.: Robustness issues in computational geometry. Technical report, Comp. 234 Final Paper, Duke University (1997)"},{"key":"8_CR6","first-page":"380","volume":"12","author":"K. Sugihara","year":"1989","unstructured":"Sugihara, K., Iri, M.: A solid modelling system free from topological inconsistency. Journal of Information Processing\u00a012, 380\u2013393 (1989)","journal-title":"Journal of Information Processing"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1142\/S0218195994000124","volume":"4","author":"K. Sugihara","year":"1994","unstructured":"Sugihara, K., Iri, M.: A robust topology-oriented incremental algorithm for voronoi diagrams. IJCGA\u00a04, 179\u2013228 (1994)","journal-title":"IJCGA"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1111\/1467-8659.1330045","volume":"13","author":"K. Sugihara","year":"1994","unstructured":"Sugihara, K.: A robust and consistent algorithm for intersecting convex polyhedra. Computer Graphics Forum\u00a013, 45\u201354 (1994)","journal-title":"Computer Graphics Forum"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55611-7","volume-title":"Axioms and Hulls","author":"D.E. Knuth","year":"1992","unstructured":"Knuth, D.E.: Axioms and Hulls. LNCS, vol.\u00a0606. Springer, Heidelberg (1992)"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1109\/12.620478","volume":"46","author":"D. Michelucci","year":"1997","unstructured":"Michelucci, D., Moreau, J.M.: Lazy arithmetic. IEEE Transactions on Computers\u00a046, 961\u2013975 (1997)","journal-title":"IEEE Transactions on Computers"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BFb0014496","volume-title":"Applied Computational Geometry. Towards Geometric Engineering","author":"A. Fabri","year":"1996","unstructured":"Fabri, A., Giezeman, G.J., Kettner, L., Schirra, S., Sch\u00f6nherr, S.: The CGAL kernel: A basis for geometric computation. In: Lin, M.C., Manocha, D. (eds.) FCRC-WS 1996 and WACG 1996. LNCS, vol.\u00a01148, pp. 191\u2013202. Springer, Heidelberg (1996)"},{"key":"8_CR12","volume-title":"C-XSC, A C++ class library for extended scientific computing","author":"K. Klatte","year":"1993","unstructured":"Klatte, K., Kulisch, U., Lawo, C., Rausch, M., Wiethoff, A.: C-XSC, A C++ class library for extended scientific computing. Springer, Heidelberg (1993)"},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1145\/336154.336196","volume-title":"Proceedings 16th Annual ACM Symposium on Computational Geometry","author":"S. Funke","year":"2000","unstructured":"Funke, S., Mehlhorn, K.: LOOK \u2013 a lazy object-oriented kernel for geometric computations. In: Proceedings 16th Annual ACM Symposium on Computational Geometry, Hong-Kong, pp. 156\u2013165. ACM Press, New York (2000)"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K. Mehlorn","year":"1995","unstructured":"Mehlorn, K., Naher, S.: LEDA: A platform for combinatorial and geometric computing. Communications of the ACM\u00a038, 96\u2013102 (1995)","journal-title":"Communications of the ACM"},{"key":"8_CR15","first-page":"1018","volume-title":"The LEDA Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., Naher, S.: The LEDA Platform for Combinatorial and Geometric Computing, 1018 pages. Cambridge University Press, Cambridge (1999)"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1145\/304893.304989","volume-title":"Proceedings 15th Annual ACM Symposium on Computational Geometry","author":"V. Karamcheti","year":"1999","unstructured":"Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A core library for robust numeric and geometric computation. In: Proceedings 15th Annual ACM Symposium on Computational Geometry, pp. 351\u2013359. ACM Press, New York (1999)"},{"key":"8_CR17","volume-title":"The complexity of robot motion planning","author":"J. Canny","year":"1988","unstructured":"Canny, J.: The complexity of robot motion planning. M.I.T. Press, Cambridge (1988)"},{"key":"8_CR18","volume-title":"Proc. 18th ACM Symp. on Computational Geometry","author":"S. Pion","year":"2003","unstructured":"Pion, S., Yap, C.: Constructive root bound method for k-ary rational input numbers. In: Proc. 18th ACM Symp. on Computational Geometry, ACM Press, San Diego, California (2003)"},{"key":"8_CR19","unstructured":"Li, C., Yap, C.: A new constructive root bound for algebraic expressions. In: 12th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2001)"},{"key":"8_CR20","series-title":"Discrete Mathematics and Theoretical Computer Science Series","volume-title":"Polynomials: An algorithmic approach","author":"M. Mignotte","year":"1999","unstructured":"Mignotte, M., Stefanescu, D.: Polynomials: An algorithmic approach. Discrete Mathematics and Theoretical Computer Science Series, vol.\u00a0XI. Springer, Heidelberg (1999)"},{"key":"8_CR21","unstructured":"Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: A strong and easily computable separation bound for arithmetic expressions involving square roots. In: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms table of contents, New Orleans, Louisiana, United States, pp. 702\u2013709 (1997)"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"489","DOI":"10.2307\/2589344","volume":"107","author":"E.R. Scheinerman","year":"2000","unstructured":"Scheinerman, E.R.: When close enough is close enough. American Mathematical Monthly\u00a0107, 489\u2013499 (2000)","journal-title":"American Mathematical Monthly"},{"key":"8_CR23","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0010-4485(03)00060-5","volume":"36","author":"J. Keyser","year":"2004","unstructured":"Keyser, J., Culver, T., Foskey, M., Krishnan, S., Manocha, D.: ESOLID - a system for exact boundary evaluation. Computer-Aided Design (Special Issue on Solid Modeling)\u00a036, 175\u2013193 (2004)","journal-title":"Computer-Aided Design (Special Issue on Solid Modeling)"},{"key":"8_CR24","volume-title":"Interval Analysis","author":"R. Moore","year":"1966","unstructured":"Moore, R.: Interval Analysis. Prentice Hall, Englewood Cliffs (1966)"},{"key":"8_CR25","unstructured":"Andrade, M.V.A., Comba, J.L.D., Stolfi, J.: Affine arithmetic. In: Abstracts of the International Conference on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL 1994), St. Petersburg (Russia), pp. 36\u201340 (1994)"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1023\/B:NUMA.0000049462.70970.b6","volume":"37","author":"L.H. Figueiredo de","year":"2004","unstructured":"de Figueiredo, L.H., Stolfi, J.: Affine arithmetic: Concepts and applications. Numerical Algorithms\u00a037, 147\u2013158 (2004)","journal-title":"Numerical Algorithms"},{"key":"8_CR27","volume-title":"Curves and Surfaces for Computer Aided Geometric Design","author":"G. Farin","year":"1990","unstructured":"Farin, G.: Curves and Surfaces for Computer Aided Geometric Design. Academic Press, London (1990)"},{"key":"8_CR28","first-page":"807","volume":"28","author":"C.Y. Hu","year":"1996","unstructured":"Hu, C.Y., Patrikalakis, N., Ye, X.: Robust interval solid modelling. part 1: Representations. Part 2: Boundary evaluation. CAD\u00a028, 807\u2013817, 819\u2013830 (1996)","journal-title":"CAD"},{"key":"8_CR29","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0167-8396(93)90019-Y","volume":"10","author":"E.C. Sherbrooke","year":"1993","unstructured":"Sherbrooke, E.C., Patrikalakis, N.: Computation of the solutions of nonlinear polynomial systems. Computer Aided Geometric Design\u00a010, 379\u2013405 (1993)","journal-title":"Computer Aided Geometric Design"},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0362-546X(01)00166-3","volume":"47","author":"J. Garloff","year":"2001","unstructured":"Garloff, J., Smith, A.P.: Investigation of a subdivision based algorithm for solving systems of polynomial equations. Journal of nonlinear analysis: Series A Theory and Methods\u00a047, 167\u2013178 (2001)","journal-title":"Journal of nonlinear analysis : Series A Theory and Methods"},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/B:REOM.0000003995.08805.2a","volume":"10","author":"P.S.V. Nataraj","year":"2004","unstructured":"Nataraj, P.S.V., Kotecha, K.: Global optimization with higher order inclusion function forms part 1: A combined Taylor-Bernstein form. Reliable Computing\u00a010, 27\u201344 (2004)","journal-title":"Reliable Computing"},{"key":"8_CR32","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1023\/A:1024618415645","volume":"9","author":"P.S.V. Nataraj","year":"2003","unstructured":"Nataraj, P.S.V., Kotecha, K.: Higher order convergence for multidimensional functions with a new Taylor-Bernstein form as inclusion function. Reliable Computing\u00a09, 185\u2013203 (2003)","journal-title":"Reliable Computing"},{"key":"8_CR33","unstructured":"Mourrain, B., Rouillier, F., Roy, M.F.: Bernstein\u2019s basis and real root isolation. Technical Report 5149, INRIA Rocquencourt (2004)"},{"key":"8_CR34","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1142\/S0218195906001914","volume":"16","author":"D. Michelucci","year":"2006","unstructured":"Michelucci, D., Foufou, S.: Interval based tracing of strange attractors. International Journal of Computational Geometry and Applications\u00a016, 27\u201339 (2006)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"8_CR35","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2495-0","volume-title":"Rigorous Global Search: Continuous Problems","author":"R. Kearfott","year":"1996","unstructured":"Kearfott, R.: Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers, Dordrecht (1996)"},{"key":"8_CR36","doi-asserted-by":"crossref","DOI":"10.1201\/9780203026922","volume-title":"Global Optimization Using Interval Analysis","author":"E.R. Hansen","year":"2003","unstructured":"Hansen, E.R., Walster, G.W.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (2003)"},{"key":"8_CR37","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(01)00091-3","volume":"2","author":"A. Edalat","year":"2002","unstructured":"Edalat, A., Lieutier, A.: Foundation of a computable solid modelling. Theoretical Computer Science\u00a02, 319\u2013345 (2002)","journal-title":"Theoretical Computer Science"},{"key":"8_CR38","volume-title":"Proc. Theory and Practice of Geometric Modeling 1996","author":"S. Foufou","year":"1996","unstructured":"Foufou, S., Brun, J., Bouras, A.: Surfaces intersection for solid algebra: A classification algorithm. In: Strasser, W., Klein, R., Rau, R. (eds.) Proc. Theory and Practice of Geometric Modeling 1996, Tubingen, Germany, Springer, Heidelberg (1996)"},{"key":"8_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis An Introduction","author":"K. Weihrauch","year":"2000","unstructured":"Weihrauch, K.: Computable Analysis An Introduction. Springer, Heidelberg (2000)"},{"key":"8_CR40","doi-asserted-by":"crossref","unstructured":"Boehm, H.J., Cartwright, R., Riggle, M., O\u2019Donnell, M.: Exact real arithmetic: a case study in higher order programming. In: Proc. ACM Conference on Lisp and Functional Programming, pp. 162\u2013173 (1986)","DOI":"10.1145\/319838.319860"},{"key":"8_CR41","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0304-3975(02)00226-8","volume":"291","author":"D. Lester","year":"2003","unstructured":"Lester, D., Gowland, P.: Using pvs to validate the algorithms of an exact arithmetic. Theoretical Computer Science\u00a0291, 203\u2013218 (2003)","journal-title":"Theoretical Computer Science"},{"key":"8_CR42","doi-asserted-by":"crossref","unstructured":"Vignes, J., Alt, R.: An efficient stochastic method for round-off error analysis. In: Accurate Scientific Computations, pp. 183\u2013205 (1985)","DOI":"10.1007\/3-540-16798-6_12"},{"key":"8_CR43","unstructured":"Michelucci, D., Moreau, J.M.: ZEA \u2013 a zero-free exact arithmetic. In: Proceedings 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, pp. 153\u2013157 (2000)"},{"key":"8_CR44","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H. Edelsbrunner","year":"1990","unstructured":"Edelsbrunner, H., M\u00fccke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph\u00a09, 66\u2013104 (1990)","journal-title":"ACM Trans. Graph"},{"key":"8_CR45","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"4","author":"J. Schwartz","year":"1980","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM\u00a04, 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"8_CR46","doi-asserted-by":"crossref","unstructured":"Agrawal, A., Requicha, A.G.: A paradigm for the robust design of algorithms for geometric modeling. In: Computer Graphics Forum (EUROGRAPHICS 1994), vol.\u00a013, pp. C\u201333\u2013C\u201344 (1994)","DOI":"10.1111\/1467-8659.1330033"},{"key":"8_CR47","first-page":"291","volume-title":"Proc. ISSAC","author":"M. Monagan","year":"1994","unstructured":"Monagan, M., Gonnet, G.: Signature functions for algebraic numbers. In: Proc. ISSAC, pp. 291\u2013296. ACM Press, New York (1994)"},{"key":"8_CR48","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF02307374","volume":"53","author":"M. Benouamer","year":"1994","unstructured":"Benouamer, M., Jaillon, P., Michelucci, D., Moreau, J.: Hashing lazy numbers. Computing\u00a053, 205\u2013217 (1994)","journal-title":"Computing"},{"key":"8_CR49","doi-asserted-by":"crossref","unstructured":"Tulone, D., Yap, C., Li, C.: Randomized zero testing of radical expressions and elementary geometry theorem proving. In: International Workshop on Automated Deduction in Geometry (ADG 2000) (2000)","DOI":"10.1007\/3-540-45410-1_5"},{"key":"8_CR50","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/32439.32465","volume-title":"SYMSAC 1986: Proceedings of the fifth ACM symposium on Symbolic and algebraic computation","author":"G.H. Gonnet","year":"1986","unstructured":"Gonnet, G.H.: New results for random determination of equivalence of expressions. In: SYMSAC 1986: Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, pp. 127\u2013131. ACM Press, New York (1986)"},{"key":"8_CR51","unstructured":"Hong, J.: Proving by example and gap theorem. In: I.C.S. (ed.): 27th symposium on Foundations of computer science, Toronto, Ontario, 107\u2013116 (in press,1986)"},{"key":"8_CR52","unstructured":"Kortenkamp, U.: Foundations of Dynamic Geometry. PhD thesis, ETH Zurich, Institut fur Theoretische Informatik (1999)"},{"key":"8_CR53","doi-asserted-by":"crossref","unstructured":"Foufou, S., Jurzak, J.P., Michelucci, D.: Numerical decomposition of geometric constraints. In: Proc. ACM Conference on Solid and Physical Modeling, pp. 143\u2013151 (2005)","DOI":"10.1145\/1060244.1060261"},{"key":"8_CR54","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete and Computational Geometry\u00a04, 387\u2013421 (1989)","journal-title":"Discrete and Computational Geometry"},{"key":"8_CR55","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K.L. Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete and Computational Geometry\u00a02, 195\u2013222 (1987)","journal-title":"Discrete and Computational Geometry"},{"key":"8_CR56","series-title":"Lecture Notes in Control and Information Science","volume-title":"Robot Motion Planning and Control","year":"1998","unstructured":"Laumond, J.P. (ed.): Robot Motion Planning and Control. Lecture Notes in Control and Information Science. Springer, Heidelberg (1998)"},{"key":"8_CR57","unstructured":"Michelucci, D., Neveu, M.: Shortest circuits with given homotopy in a constellation. In: 9th ACM Symp. Solid Modeling and Applications, pp. 297\u2013302 (2004)"},{"key":"#cr-split#-8_CR58.1","doi-asserted-by":"crossref","unstructured":"Choi, J., Sellen, J., Yap, C.: Approximate Euclidean shortest path in 3-space. Int???l. J. Computational Geometry and Applications 271???295 (1997);","DOI":"10.1142\/S0218195997000181"},{"key":"#cr-split#-8_CR58.2","unstructured":"Journal special issue. Also in 10th ACM Symposium on Computational Geometry (1994)"},{"key":"8_CR59","unstructured":"Glassner, A.: An Introduction to Ray Tracing. In: Glassner, A. (ed.), Academic Press, London (1989) ISBN 0-12-286160-4"},{"key":"8_CR60","volume-title":"Principles of Digital Image Synthesis","author":"A.S. Glassner","year":"1994","unstructured":"Glassner, A.S.: Principles of Digital Image Synthesis. Morgan Kaufmann Publishers Inc., San Francisco (1994)"}],"container-title":["Lecture Notes in Computer Science","Reliable Implementation of Real Number Algorithms: Theory and Practice"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85521-7_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T04:50:03Z","timestamp":1631595003000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85521-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540855200","9783540855217"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85521-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}