{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:24:36Z","timestamp":1761611076451,"version":"3.43.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2000,2,1]],"date-time":"2000-02-01T00:00:00Z","timestamp":949363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2000,2,1]],"date-time":"2000-02-01T00:00:00Z","timestamp":949363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Reliable Computing"],"published-print":{"date-parts":[[2000,2]]},"DOI":"10.1023\/a:1009934225596","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T19:25:11Z","timestamp":1040585111000},"page":"39-60","source":"Crossref","is-referenced-by-count":14,"title":["Exact Computation of Delaunay and Power Triangulations"],"prefix":"10.1007","volume":"6","author":[{"given":"Marina","family":"Gavrilova","sequence":"first","affiliation":[]},{"given":"Helmut","family":"Ratschek","sequence":"additional","affiliation":[]},{"given":"Jon G.","family":"Rokne","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"260004_CR1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/0216006","volume":"16","author":"F. Aurenhammer","year":"1987","unstructured":"Aurenhammer, F.: Power Diagrams: Properties, Algorithms, and Applications, SIAM Journal of Computing\n16 (1987), pp. 78-96.","journal-title":"SIAM Journal of Computing"},{"key":"260004_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01840356","volume":"2","author":"R. Dwyer","year":"1987","unstructured":"Dwyer, R.: A Fast Divide and Conquer Algorithm for Constructing Delaunay Triangulations, Algorithmica\n2 (1987), pp. 137-151.","journal-title":"Algorithmica"},{"key":"260004_CR3","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02574694","volume":"6","author":"R. Dwyer","year":"1991","unstructured":"Dwyer, R.: Higher-Dimensional Voronoi Diagrams in Linear Expected Time, Discrete and Computational Geometry\n6 (1991), pp. 343-367.","journal-title":"Discrete and Computational Geometry"},{"key":"260004_CR4","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H. and M\u00fccke, E.: Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms, in: Proceedings of the 4th Annual ACM Symposium on Computational Geometry, 1988, pp. 118-133.","DOI":"10.1145\/73393.73406"},{"key":"260004_CR5","first-page":"83","volume-title":"Proceedings Mathematics of Surfaces III","author":"R. Farouki","year":"1989","unstructured":"Farouki, R.: Numerical Stability in Geometric Algorithms and Representations, in: Hanscomb, D. C. (ed.), Proceedings Mathematics of Surfaces III, Oxford University Press, New York, 1989, pp. 83-113."},{"key":"260004_CR6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1142\/S0218195995000118","volume":"6","author":"S. Fortune","year":"1995","unstructured":"Fortune, S.: Numerical Stability of Algorithms for 2D Delaunay Triangulations, International Journal of Computational Geometry and Applications\n6 (1995), pp. 193-213.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"260004_CR7","doi-asserted-by":"crossref","unstructured":"Fortune, S.: Stable Maintenance of Point Set Triangulations in Two Dimensions, in: 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 494-499.","DOI":"10.1109\/SFCS.1989.63524"},{"key":"260004_CR8","doi-asserted-by":"crossref","unstructured":"Fortune, S. and Wyk, C.: Efficient Exact Arithmetic for Computational Geometry, in: Proceedings of the 4th Annual ACM Symposium on Computational Geometry, 1993, pp. 163-172.","DOI":"10.1145\/160985.161015"},{"key":"260004_CR9","first-page":"3","volume":"11","author":"M. Gavrilova","year":"1996","unstructured":"Gavrilova, M. and Rokne, J.: An Efficient Algorithm for Construction of the Power Diagram from the Voronoi Diagram in the Plane, International Journal of Computer Mathematics\n11 (1996), pp. 3-4.","journal-title":"International Journal of Computer Mathematics"},{"issue":"2","key":"260004_CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1145\/282918.282923","volume":"4","author":"L. Guibas","year":"1985","unstructured":"Guibas, L. and Stolfi, J.: Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagram, ACM Transactions on Graphics\n4(2) (1985), pp. 75-123.","journal-title":"ACM Transactions on Graphics"},{"key":"260004_CR11","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF01758770","volume":"7","author":"L. Guibas","year":"1992","unstructured":"Guibas, L., Knuth, D., and Sharir, M.: Randomized Incremental Construction of Delaunay and Voronoi Diagram, Algorithmica\n7 (1992), pp. 381-413.","journal-title":"Algorithmica"},{"key":"260004_CR12","volume-title":"Geometric and Solid Modeling","author":"C. Hoffmann","year":"1989","unstructured":"Hoffmann, C.: Geometric and Solid Modeling, Morgan Kaufmann, San Mateo, CA, 1989."},{"key":"260004_CR13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/2.16223","volume":"22","author":"C. Hoffmann","year":"1989","unstructured":"Hoffmann, C.: The Problem of Accuracy and Robustness in Geometric Computation, IEEE Computing\n22 (1989), pp. 31-42.","journal-title":"IEEE Computing"},{"key":"260004_CR14","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF02242021","volume":"47","author":"K. J\u00fcnger","year":"1991","unstructured":"J\u00fcnger, K., Reinelt, G., and Zepf, D.: Computing Correct Delaunay Triangulations, Computing\n47 (1991), pp. 43-49.","journal-title":"Computing"},{"key":"260004_CR15","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF02017351","volume":"30","author":"T. Kao","year":"1990","unstructured":"Kao, T. and Knott, G.: An Efficient and Numerically Correct Algorithm for the 2D Convex Hull Problem, BIT\n30 (1990), pp. 311-331.","journal-title":"BIT"},{"key":"260004_CR16","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/99902.99905","volume":"10","author":"M. Karasick","year":"1991","unstructured":"Karasick, M., Lieber, D., and Nackman, L.: Efficient Delaunay Triangulation Using Rational Arithmetic, ACM Transactions of Graphics\n10 (1991), pp. 71-91.","journal-title":"ACM Transactions of Graphics"},{"key":"260004_CR17","first-page":"275","volume":"11","author":"J. Katajainen","year":"1988","unstructured":"Katajainen, J. and Koppinen, M.: Constructing Delaunay Triangulations by Merging Buckets in Quadtree Order, Annales Sociatatis Mathematicae Polonae, Series IV, Fundamenta Informaticae\n11 (1988), pp. 275-288.","journal-title":"Annales Sociatatis Mathematicae Polonae, Series IV, Fundamenta Informaticae"},{"key":"260004_CR18","doi-asserted-by":"crossref","unstructured":"Li, Z. and Milenkovic, V.: Constructing Strongly Convex Hulls Using Exact or Rounded Arithmetic, in: Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 235-243.","DOI":"10.1145\/98524.98577"},{"key":"260004_CR19","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01937482","volume":"24","author":"A. Maus","year":"1984","unstructured":"Maus, A.: Delaunay Triangulation and the Convex Hull of n Points in Expected Linear Time, BIT\n24 (1984), pp. 151-163.","journal-title":"BIT"},{"key":"260004_CR20","doi-asserted-by":"crossref","unstructured":"Milenkovic, V.: Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections in Rounded Arithmetic, in: Proceedings of 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 500-505.","DOI":"10.1109\/SFCS.1989.63525"},{"key":"260004_CR21","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0004-3702(88)90061-6","volume":"37","author":"V. Milenkovic","year":"1988","unstructured":"Milenkovic, V.: Verifiable Implementations of Geometric Algorithms Using Finite-Precision Arithmetic, Artificial Intelligence\n37 (1988), pp. 377-401.","journal-title":"Artificial Intelligence"},{"key":"260004_CR22","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1006\/gmip.1995.1027","volume":"57","author":"Y. Oishi","year":"1995","unstructured":"Oishi, Y. and Sugihara, K.: Topology-Oriented Divide-and-Conquer Algorithm for Voronoi Diagrams, Graphics Models and Image Processing\n57 (1995), pp. 303-314.","journal-title":"Graphics Models and Image Processing"},{"key":"260004_CR23","first-page":"205","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A. Okabe","year":"1992","unstructured":"Okabe, A., Boots, B., and Sugihara, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, Chichester, West Sussex, England, 1992, pp. 205-208."},{"key":"260004_CR24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0096-3003(98)00010-1","volume":"99","author":"H. Ratschek","year":"1999","unstructured":"Ratschek, H. and Rokne, J.: Determination of the Exact Sign of a Sum, Applied Maths. and Comp.\n99 (1999), pp. 99-127.","journal-title":"Applied Maths. and Comp."},{"key":"260004_CR25","unstructured":"Salesin, D.: Epsilon Geometry: Building Robust Algorithms for Imprecise Computations, Ph.D. Thesis, Stanford University, 1991."},{"key":"260004_CR26","doi-asserted-by":"crossref","unstructured":"Su, P. and Drysdale, R.: A Comparison of Sequential Delaunay Triangulation Algorithms, in: Proceedings of the 11th Annual Symposium on Computational Geometry, 1995, pp. 61-70.","DOI":"10.1145\/220279.220286"},{"key":"260004_CR27","first-page":"468","volume":"E75-A","author":"K. Sugihara","year":"1992","unstructured":"Sugihara, K.: A Simple Method for Avoiding Numerical Errors and Degeneracy in Voronoi Diagram Construction, IEICE Trans. Fundamentals E75-A (1992), pp. 468-477.","journal-title":"IEICE Trans. Fundamentals"},{"key":"260004_CR28","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1142\/S0218195994000124","volume":"4","author":"K. Sugihara","year":"1994","unstructured":"Sugihara, K. and Iri, M.: A Robust Topology-Oriented Incremental Algorithm for Voronoi Diagrams, International Journal of Computational Geometry and Applications\n4 (1994), pp. 179-228.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"260004_CR29","doi-asserted-by":"crossref","unstructured":"Yap, C.: A Geometric Consistency Theorem for a Symbolic Perturbation Theorem, in: Proceedings of the 4th Annual ACM Symposium on Computational Geometry, 1988, pp. 134-142.","DOI":"10.1145\/73393.73407"}],"container-title":["Reliable Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009934225596.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009934225596\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009934225596.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T09:41:47Z","timestamp":1754473307000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009934225596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,2]]}},"alternative-id":["260004"],"URL":"https:\/\/doi.org\/10.1023\/a:1009934225596","relation":{},"ISSN":["1385-3139","1573-1340"],"issn-type":[{"type":"print","value":"1385-3139"},{"type":"electronic","value":"1573-1340"}],"subject":[],"published":{"date-parts":[[2000,2]]}}}