{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:45Z","timestamp":1759638645576},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422327"},{"type":"electronic","value":"9783540455455"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45545-0_10","type":"book-chapter","created":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T19:01:49Z","timestamp":1195239709000},"page":"12-26","source":"Crossref","is-referenced-by-count":7,"title":["Robust Geometric Computation Based on Topological Consistency"],"prefix":"10.1007","author":[{"given":"Kokichi","family":"Sugihara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,17]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"M. Benouamer, D. Michelucci and B. Peroche: Error-free boundary evaluation using lazy rational arithmetic \u2014A detailed implementation. Proceedings of the 2nd Symposium on Solid Modeling and Applications, Montreal, 1993, pp. 115\u2013126.","DOI":"10.1145\/164360.164403"},{"key":"10_CR2","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. Proceedings of the 13th Annual ACM Symposium on Computational Geometry, Nice, June 1997, pp. 1\u2013182.","DOI":"10.1145\/262839.262948"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann and M. Yvinec: Efficient exact evaluation of signs of determinants. Proceedings of the 13th Annual ACM Symposium on Computational Geometry, Nice, June 1997, pp. 166\u2013173.","DOI":"10.1145\/262839.262944"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson: Safe and effective determinant evaluation. Proceedings of the 33rd IEEE Symposium on Foundation of Computer Science, pp. 387\u2013395.","DOI":"10.1109\/SFCS.1992.267751"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"D. Dobkin and D. Silver: Recipes for geometric and numerical analysis\u2014Part I, An empirical study. Proceedings of the 4th ACM Annual Symposium on Computational Geometry, Urbana-Champaign, 1988, pp. 93\u2013105.","DOI":"10.1145\/73393.73404"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner and E. P. M\u00fccke: Simulation of simplicity\u2014A technique to cope with degenerate cases in geometric algorithms. Proceedings of the 4th ACM Annual Symposium on Computational Geometry, Urbana-Champaign, 1988, pp. 118\u2013133.","DOI":"10.1145\/73393.73406"},{"key":"10_CR7","first-page":"91","volume-title":"Geometric Modeling\u2014Algorithms and New Trends","author":"D. A. Field","year":"1987","unstructured":"D. A. Field: Mathematical problems in solid modeling\u2014A brief survey. G. E. Farin (ed.), Geometric Modeling\u2014Algorithms and New Trends, SIAM, Philadelphia, 1987, pp. 91\u2013107."},{"key":"10_CR8","first-page":"94","volume-title":"Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer Science","author":"S. Fortune","year":"1989","unstructured":"S. Fortune: Stable maintenance of point-set triangulations in two dimensions. Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer Science, Research Triangle Park, California, 1989, pp.94\u2013499."},{"key":"10_CR9","doi-asserted-by":"publisher","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. International Journal of Computational Geometry and Applications, vol. 5 (1995), pp. 193\u2013213.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"S. Fortune and C. von Wyk: Efficient exact arithmetic for computational geometry. Proceedings of the 9th ACM Annual Symposium on Computational Geometry, San Diego, 1993, pp. 163\u2013172.","DOI":"10.1145\/160985.161015"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"D. H. Greene and F. Yao: Finite resolution computational geometry. Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, Toronto, October 1986, pp. 3\u2013152.","DOI":"10.1109\/SFCS.1986.19"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"L. Guibas, D. Salesin and J. Stolfi: Epsilon geometry\u2014Building robust algorithms from imprecise computations. Proc. 5th ACM Annual Symposium on Computational Geometry (Saarbr\u00fccken, May 1989), pp. 208\u2013217.","DOI":"10.1145\/73833.73857"},{"key":"10_CR13","first-page":"627","volume":"E83-A","author":"T. Hiroshima","year":"2000","unstructured":"T. Hiroshima, Y. Miyamoto and K. Sugihara: Another proof of polynomial-time recognizability of Delaunay graphs. IEICE Transactions on Fundamentals, Vol. E83-A (2000), pp. 627\u2013638.","journal-title":"IEICE Transactions on Fundamentals"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1090\/S0273-0979-1992-00303-8","volume":"27","author":"C. D. Hodgson","year":"1992","unstructured":"C. D. Hodgson, I. Rivin and W. D. Smith: A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere. Bulletin of the American Mathematical Society, vol. 27 (1992), pp. 6\u2013251.","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"3","key":"10_CR15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/2.16223","volume":"22","author":"C. M. Hoffmann","year":"1989","unstructured":"C. M. Hoffmann: The problems of accuracy and robustness in geometric computation. IEEE Computer, vol. 22, no. 3 (March 1989), pp. 31\u20131.","journal-title":"IEEE Computer"},{"key":"10_CR16","volume-title":"Geometric and Solid Modeling","author":"C. M. Hoffmann","year":"1989","unstructured":"C. M. Hoffmann: Geometric and Solid Modeling. Morgan Kaufmann Publisher, San Mateo, 1989."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"T. Imai: A topology-oriented algorithm for the Voronoi diagram of polygon. Proceedings of the 8th Canadian Conference on Computational Geometry, 1996, pp. 107\u2013112.","DOI":"10.1515\/9780773591134-021"},{"key":"10_CR18","unstructured":"T. Imai: How to get the sign of integers from their residuals. Abstracts of the 9th Franco-Japan Days on Combinatorics and Optimization, 1996, p. 7."},{"key":"10_CR19","unstructured":"H. Inagaki and K. Sugihara: Numerically robust algorithm for constructing constrained Delaunay triangulation. Proceedings of the 6th Canadian Conference on Computational Geometry, Saskatoon, August 19, pp. 171\u2013176."},{"key":"10_CR20","unstructured":"H. Inagaki, K. Sugihara and N. Sugie, N.: Numerically robust incremental algorithm for constructing three-dimensional Voronoi diagrams. Proceedings of the 6th Canadian Conference Computational Geometry, Newfoundland, August 1992, pp. 3\u2013339."},{"key":"10_CR21","unstructured":"M. Karasick, D. Lieber and L. R. Nackman: Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics, vol. 10 (1991), pp. 71au]-91."},{"key":"10_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55611-7","volume-title":"Axioms and Hulls","author":"D. E. Knuth","year":"1992","unstructured":"D. E. Knuth: Axioms and Hulls. Lecture Notes in Computer Science, no. 606, Springer-Verlag, Berlin, 1992."},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"G. Liotta, F. P. Preparata and R. Tamassia: Robust proximity queries \u2014 An illustration of degree-driven algorithm design. Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 1997, pp. 156\u2013165.","DOI":"10.1145\/262839.262922"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and S. N\u00e4her: A platform for combinatorial and geometric computing. Communications of the ACM, January 1995, pp. 96\u2013102.","DOI":"10.1145\/204865.204889"},{"key":"10_CR25","doi-asserted-by":"publisher","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, vol. 37 (1988), pp. 377\u201301.","journal-title":"Artificial Intelligence"},{"key":"10_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-63890-3_30","volume-title":"Algorithms and Computation, 8th International Symposium, ISAAC\u201997","author":"T. Minakawa","year":"1997","unstructured":"T. Minakawa and K. Sugihara: Topology oriented vs. exact arithmetic\u2014experience in implementing the three-dimensional convex hull algorithm. H. W. Leong, H. Imai and S. Jain (eds.), Algorithms and Computation, 8th International Symposium, ISAAC\u201997 (Lecture Notes in Computer Science 1350), (December, 1997, Singapore), pp. 273\u2013282."},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1080\/10556789808805719","volume":"10","author":"T. Minakawa","year":"1998","unstructured":"T. Minakawa and K. Sugihara: Topology-oriented construction of threedimensional convex hulls. Optimization Methods and Software, vol. 10 (1998), pp. 357\u2013371.","journal-title":"Optimization Methods and Software"},{"key":"10_CR28","first-page":"303","volume":"57","author":"Y. Oishi","year":"1995","unstructured":"Y. Oishi and K. Sugihara: Topology-oriented divide-and-conquer algorithm for Voronoi diagrams. Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, vol. 57 (1995), pp. 303\u20133.","journal-title":"Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"T. Ottmann, G. Thiemt and C. Ullrich: Numerical stability of geometric algorithms. Proceedings of the 3rd ACM Annual Symposium on Computational Geometry, Waterloo, 1987, pp. 119\u2013125.","DOI":"10.1145\/41958.41970"},{"key":"10_CR30","unstructured":"P. Schorn: Robust algorithms in a program library for geometric computation. Dissertation submitted to the Swiss Federal Institute of Technology (ETH) Z\u00fcrich for the degree of Doctor of Technical Sciences, 1991."},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"M. Segal and C. H. Sequin: Consistent calculations for solid modeling. Proceedings of the ACM Annual Symposium on Computational Geometry, Baltimore, 1985, pp. 29\u201338.","DOI":"10.1145\/323233.323238"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"J. R. Shewchuk: Robust adaptive floating-point geometric predicates. Proceedings of the 12th Annual ACM Symposium on Computational Geometry, Philadelphia, May 1996, pp. 1\u2013150.","DOI":"10.1145\/237218.237337"},{"key":"10_CR33","unstructured":"E. Steinitz: Polyheder und Raumeinteilungen. Encyklop\u00e4die der mathematischen Wissenchaften, Band III, Teil 1, 2. H\u00e4lfte, IIIAB12, pp. 1\u2013139."},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"A. J. Steward: Local robustness and its application to polyhedral intersection. International Journal of Computational Geometry and Applications, vol. (1994), pp. 87\u2013118.","DOI":"10.1142\/S0218195994000070"},{"key":"10_CR35","first-page":"68","volume":"E75-A","author":"K. Sugihara","year":"1992","unstructured":"K. Sugihara: A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E75-A (1992), pp.68\u2013477.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"issue":"2","key":"10_CR36","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1109\/38.124289","volume":"12","author":"K. Sugihara","year":"1992","unstructured":"K. Sugihara: An intersection algorithm based on Delaunay triangulation. IEEE Computer Graphics and Applications, vol. 12, no. 2 (March 1992), pp. 59\u201367.","journal-title":"IEEE Computer Graphics and Applications"},{"key":"10_CR37","first-page":"522","volume":"55","author":"K. Sugihara","year":"1993","unstructured":"K. Sugihara: Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams. Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, vol. 55 (1993), pp. 522\u2013531.","journal-title":"Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"K. Sugihara: A robust and consistent algorithm for intersecting convex polyhedra. Computer Graphics Forum, EUROGRAPHICS\u201994, Oslo, 1994, pp. C-45\u2013C-54.","DOI":"10.1111\/1467-8659.1330045"},{"key":"10_CR39","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/S0022-0000(05)80056-X","volume":"9","author":"K. Sugihara","year":"1994","unstructured":"K. Sugihara: Robust gift wrapping for the three-dimensional convex hull. Journal of Computer and System Sciences, vol.9 (1994), pp. 391\u2013407.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR40","doi-asserted-by":"crossref","unstructured":"K. Sugihara: Experimental study on acceleration of an exact-arithmetic geometric algorithm. Proceedings of the 1997 International Conference on Shape Modeling and Applications, Aizu-Wakamatsu, 1997, pp. 160\u2013168.","DOI":"10.1109\/SMA.1997.634893"},{"key":"10_CR41","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, vol. 12 (1989), pp. 380\u2013393.","journal-title":"Journal of Information Processing"},{"key":"10_CR42","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1109\/5.163412","volume":"80","author":"K. Sugihara","year":"1992","unstructured":"K. Sugihara and M. Iri: Construction of the Voronoi diagram for \u201cone million\u201d generators in single-precision arithmetic. Proceedings of the IEEE, vol. 80 (1992), pp. 71\u20131484.","journal-title":"Proceedings of the IEEE"},{"key":"10_CR43","doi-asserted-by":"crossref","unstructured":"K. Sugihara and M. Iri: A robust topology-oriented incremental algorithm for Voronoi diagrams. International Journal of Computational Geometry and Applications, vol. (1994), pp. 179\u2013228.","DOI":"10.1142\/S0218195994000124"},{"key":"10_CR44","doi-asserted-by":"crossref","unstructured":"C. K. Yap: A geometric consistency theorem for a symbolic perturbation scheme. Proceedings of the 4th Annual ACM Symposium on Computational Geometry, Urbana-Champaign, 1988, pp. 1\u2013142.","DOI":"10.1145\/73393.73407"},{"key":"10_CR45","first-page":"52","volume-title":"Computing in Euclidean Geometry","author":"C. K. Yap","year":"1995","unstructured":"C. K. Yap: The exact computation paradigm. D.-Z. Du and F. Hwang (eds.), Computing in Euclidean Geometry, 2nd edition. World Scientific, Singapore, 1995, pp.52\u2013492.","edition":"2nd edition"},{"key":"10_CR46","doi-asserted-by":"crossref","unstructured":"X. Zhu, S. Fang and B. D. Br\u00fcderlin: Obtaining robust Boolean set operations for manifold solids by avoiding and eliminating redundancy. Proceedings of the 2nd Symposium on Solid Modeling and Applications, Montreal, May 1993, pp. 7\u2013154.","DOI":"10.1145\/164360.164413"}],"container-title":["Lecture Notes in Computer Science","Computational Science \u2014 ICCS 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45545-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T05:26:58Z","timestamp":1708320418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45545-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422327","9783540455455"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/3-540-45545-0_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}