{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:24:11Z","timestamp":1725495851209},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540669166"},{"type":"electronic","value":"9783540466321"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46632-0_36","type":"book-chapter","created":{"date-parts":[[2007,11,24]],"date-time":"2007-11-24T19:45:01Z","timestamp":1195933501000},"page":"357-366","source":"Crossref","is-referenced-by-count":1,"title":["Topology-Oriented Approach to Robust Geometric Computation"],"prefix":"10.1007","author":[{"given":"Kokichi","family":"Sugihara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"M. Benouamer, D. Michelucci and B. Peroche: Error-free boundary evaluation using lazy rational arithmetic-A detailed implementation. Proceedings of the 2nd Symposium on Solid Modeling and Applications, Montreal, 1993, pp. 115\u2013126.","DOI":"10.1145\/164360.164403"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1109\/SFCS.1989.63524","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. 494\u2013499."},{"key":"36_CR3","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":"36_CR4","doi-asserted-by":"crossref","unstructured":"L. Guibas, D. Salesin and J. Stolfi: Epsilon geometry-Building 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":"36_CR5","doi-asserted-by":"crossref","unstructured":"C. M. Hoffmann: The problems of accuracy and robustness in geometric computation. IEEE Computer, vol. 22, no. 3 (March 1989), pp. 31\u201341.","DOI":"10.1109\/2.16223"},{"key":"36_CR6","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":"36_CR7","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":"36_CR8","unstructured":"H. Inagaki, K. Sugihara and N. Sugie, N.: Numerically robust incremental algorithm for constructing three-dimensional Voronoi diagrams. Proceedings of the 4th Canadian Conference Computational Geometry, Newfoundland, August 1992, pp. 334\u2013339."},{"key":"36_CR9","unstructured":"M. Karasick, D. Lieber and L. R. Nackman: Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics, vol. 10 (1991), pp. 71\u201391."},{"key":"36_CR10","unstructured":"V. Milenkovic: Verifiable implementations of geometric algorithms using finite precision arithmetic. Artificial Intelligence, vol. 37 (1988), pp. 377\u2013401."},{"key":"36_CR11","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":"36_CR12","unstructured":"T. Minakawa and K. Sugihara: Topology-oriented construction of three-dimensional convex hulls. Optimization Methods and Software, vol. 10 (1998), pp. 357\u2013371."},{"key":"36_CR13","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\u2013314."},{"key":"36_CR14","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":"36_CR15","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":"36_CR16","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":"36_CR17","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. 468\u2013477."},{"key":"36_CR18","unstructured":"K. Sugihara: Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams. CVGIP: Graphical Models and Image Processing, vol. 55 (1993), pp. 522\u2013531."},{"key":"36_CR19","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\u201345\u2013C\u201354.","DOI":"10.1111\/1467-8659.1330045"},{"key":"36_CR20","unstructured":"K. Sugihara: Robust gift wrapping for the three-dimensional convex hull. J. Computer and System Sciences, vol. 49 (1994), pp. 391\u2013407."},{"key":"36_CR21","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":"36_CR22","unstructured":"K. Sugihara and H. Inagaki: Why is the 3d Delaunay triangulation difficult to construct? Information Processing Letters, vol. 54 (1995), pp. 275\u2013280."},{"key":"36_CR23","unstructured":"K. Sugihara and M. Iri: A solid modelling system free from topological inconsistency. Journal of Information Processing, vol. 12 (1989), pp. 380\u2013393."},{"key":"36_CR24","doi-asserted-by":"crossref","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. 1471\u20131484.","DOI":"10.1109\/5.163412"},{"key":"36_CR25","unstructured":"K. Sugihara and M. Iri: A robust topology-oriented incremental algorithm for Voronoi diagrams. International Journal of Computational Geometry and Applications, vol. 4 (1994), pp. 179\u2013228."},{"key":"36_CR26","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1142\/9789812831699_0011","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. 452\u2013492.","edition":"2nd edition"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46632-0_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T15:18:02Z","timestamp":1708355882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46632-0_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540669166","9783540466321"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-46632-0_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}