{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T05:58:01Z","timestamp":1777528681873,"version":"3.51.4"},"reference-count":23,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1016\/0020-0190(95)00028-b","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T02:04:31Z","timestamp":1027649071000},"page":"275-280","source":"Crossref","is-referenced-by-count":20,"title":["Why is the 3D Delaunay triangulation difficult to construct?"],"prefix":"10.1016","volume":"54","author":[{"given":"Kokichi","family":"Sugihara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Inagaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0020-0190(95)00028-B_BIB1","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","article-title":"Voronoi diagrams \u2014 A survey of a fundamental geometric data structure","volume":"23","author":"Aurenhammer","year":"1991","journal-title":"ACM Comput. Surveys"},{"key":"10.1016\/0020-0190(95)00028-B_BIB2","series-title":"Algorithms in Combinatorial Geometry","author":"Edelsbrunner","year":"1987"},{"key":"10.1016\/0020-0190(95)00028-B_BIB3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF02122779","article-title":"An acyclicity theorem for cell complexes in d dimensions","volume":"10","author":"Edelsbrunner","year":"1990","journal-title":"Combinatorica"},{"key":"10.1016\/0020-0190(95)00028-B_BIB4","series-title":"Proc. 4th ACM Ann. Symp. on Computational Geometry","first-page":"118","article-title":"Simulation of simplicity \u2014 A technique to cope with degenerate cases in geometric algorithms","author":"Edelsbrunner","year":"1988"},{"key":"10.1016\/0020-0190(95)00028-B_BIB5","series-title":"Proc. 8th ACM Ann. Symp. on Computational Geometry","first-page":"74","article-title":"An efficient approach to removing geometric degeneracies","author":"Emiris","year":"1992"},{"key":"10.1016\/0020-0190(95)00028-B_BIB6","series-title":"Proc. 30th IEEE Ann. Symp. on Foundation of Computer Science","first-page":"494","article-title":"Stable maintenance of point set triangulations in two dimensions","author":"Fortune","year":"1989"},{"issue":"3","key":"10.1016\/0020-0190(95)00028-B_BIB7","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/2.16223","article-title":"The problems of accuracy and robustness in geometric computation","volume":"22","author":"Hoffmann","year":"1989","journal-title":"Computer"},{"key":"10.1016\/0020-0190(95)00028-B_BIB8","series-title":"Proc. 6th Canadian Conf. on Computational Geometry","article-title":"Numerically robust algorithm for constructing constrained Delaunay triangulation","author":"Inagaki","year":"1994"},{"key":"10.1016\/0020-0190(95)00028-B_BIB9","series-title":"Proc. 4th Canadian Conf. on Computational Geometry","first-page":"334","article-title":"Numerically robust incremental algorithm for constructing three-dimensional Voronoi diagrams","author":"Inagaki","year":"1992"},{"key":"10.1016\/0020-0190(95)00028-B_BIB10","article-title":"Axioms and Hulls","volume":"606","author":"Knuth","year":"1992"},{"key":"10.1016\/0020-0190(95)00028-B_BIB11","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/99902.99905","article-title":"Efficient Delaunay triangulation using rational arithmetic","volume":"10","author":"Karasick","year":"1991","journal-title":"ACM Trans. Graphics"},{"key":"10.1016\/0020-0190(95)00028-B_BIB12","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF00977785","article-title":"Two algorithms for constructing the Delaunay triangulations","volume":"9","author":"Lee","year":"1980","journal-title":"Internat. J. Comput. Inform. Sci."},{"key":"10.1016\/0020-0190(95)00028-B_BIB13","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0004-3702(88)90061-6","article-title":"Verifiable implementations of geometric algorithms using finite precision arithmetic","volume":"37","author":"Milenkovic","year":"1988","journal-title":"Artificial Intelligence"},{"key":"10.1016\/0020-0190(95)00028-B_BIB14","series-title":"Spatial Tessellations \u2014 Concepts and Applications of Voronoi Diagrams","author":"Okabe","year":"1992"},{"key":"10.1016\/0020-0190(95)00028-B_BIB15","first-page":"306","article-title":"Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms","volume":"27","author":"Ohya","year":"1984","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"10.1016\/0020-0190(95)00028-B_BIB16","series-title":"Computational Geometry \u2014 An Introduction","author":"Preparata","year":"1985"},{"key":"10.1016\/0020-0190(95)00028-B_BIB17","article-title":"Robust algorithms in a program library for geometric computation","author":"Schorn","year":"1991","journal-title":"Dissertation submitted to the Swiss Federal Institute of Technology (ETH) Z\u00fcrich for the degree of Doctor of Technical Sciences Diss ETH Nr. 9519"},{"key":"10.1016\/0020-0190(95)00028-B_BIB18","first-page":"468","article-title":"A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction","volume":"E75-A","author":"Sugihara","year":"1992","journal-title":"IEICE Trans. Found. Electr., Commun. Comput. Sci."},{"key":"10.1016\/0020-0190(95)00028-B_BIB19","first-page":"380","article-title":"A solid modelling system free from topological inconsistency","volume":"12","author":"Sugihara","year":"1989","journal-title":"J. Inform. Process."},{"key":"10.1016\/0020-0190(95)00028-B_BIB20","first-page":"1471","article-title":"Construction of the Voronoi diagram for \u201cone million\u201d generators in single-precision arithmetic","volume":"80","author":"Sugihara","year":"1992"},{"key":"10.1016\/0020-0190(95)00028-B_BIB21","doi-asserted-by":"crossref","DOI":"10.1142\/S0218195994000124","article-title":"A robust topology-oriented incremental algorithm for Voronoi diagrams","volume":"4","author":"Sugihara","year":"1994","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/0020-0190(95)00028-B_BIB22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1093\/comjnl\/24.2.167","article-title":"Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes","volume":"24","author":"Watson","year":"1981","journal-title":"Comput. J."},{"key":"10.1016\/0020-0190(95)00028-B_BIB23","series-title":"Proc. 4th ACM Ann. Symp. on Computational Geometry","first-page":"134","article-title":"A geometric consistency theorem for a symbolic perturbation scheme","author":"Yap","year":"1988"}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002001909500028B?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002001909500028B?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T02:58:58Z","timestamp":1555297138000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/002001909500028B"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["002001909500028B"],"URL":"https:\/\/doi.org\/10.1016\/0020-0190(95)00028-b","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}