{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:36Z","timestamp":1771036356946,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540633976","type":"print"},{"value":"9783540695363","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63397-9_35","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"459-471","source":"Crossref","is-referenced-by-count":14,"title":["Linear-time reconstruction of Delaunay triangulations with applications"],"prefix":"10.1007","author":[{"given":"Jack","family":"Snoeyink","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"van Kreveld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"issue":"3","key":"35_CR1","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"Franz Aurenhammer. Voronoi diagrams-A survey of a fundamental geometric data structure. ACM Computing Surveys, 23(3):345\u2013405, 1991.","journal-title":"ACM Computing Surveys"},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"Marshall Bern and David Eppstein. Mesh generation and optimal triangulation. In F. K. Hwang and D.-Z. Du, editors, Computing in Euclidean Geometry. World Scientific, March 1992.","DOI":"10.1142\/9789814355858_0002"},{"key":"35_CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N. Chiba","year":"1981","unstructured":"Norishige Chiba, Takao Nishizeki, and Nobuji Saito. A linear 5-coloring algorithm of planar graphs. Journal of Algorithms, 2:317\u2013327, 1981.","journal-title":"Journal of Algorithms"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, R. van Oostrum, and M. Overmans. Simple traversal of a subdivision without extra storage. Int. J. of GIS, 11, 1997.","DOI":"10.1080\/136588197242310"},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"M. Deering. Geometry compression. Computer Graphics, pages 13\u201320, 1995. Proceedings of SIGGRAPH `95.","DOI":"10.1145\/218380.218391"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"H. Djidjev and A. Lingas. On computing the Voronoi diagram for restricted planar figures. In WADS '91: Second Workshop on Data Structures and Algorithms, number 519 in Lecture Notes in Computer Science, pages 54\u201364. Springer-Verlag, 1991.","DOI":"10.1007\/BFb0028250"},{"key":"35_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987."},{"issue":"1","key":"35_CR8","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H. Edelsbrunner","year":"1990","unstructured":"Herbert Edelsbrunner and Ernst Peter M\u00fccke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 9(1):66\u2013104, 1990.","journal-title":"ACM Transactions on Graphics"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Michael T. Goodrich and Roberto Tamassia. Dynamic trees and dynamic point location. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 523\u2013533, 1991. To appear in SIAM Journal on Computing, 1997.","DOI":"10.1145\/103418.103472"},{"key":"35_CR10","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF01758770","volume":"7","author":"L. J. Guibas","year":"1992","unstructured":"L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381\u2013413, 1992.","journal-title":"Algorithmica"},{"issue":"2","key":"35_CR11","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. Guibas","year":"1985","unstructured":"Leonidas Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):74\u2013123, 1985.","journal-title":"ACM Transactions on Graphics"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"H. Hoppe. Progressive meshes. Computer Graphics, pages 99\u2013108, 1996. Proceedings of SIGGRAPH `96.","DOI":"10.1145\/237170.237216"},{"key":"35_CR13","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12:28\u201335, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"35_CR14","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1109\/TC.1984.1676388","volume":"C-33","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata. Computational geometry: a survey. IEEE Trans. Comput., C-33:1072\u20131101, 1984.","journal-title":"IEEE Trans. Comput."},{"key":"35_CR15","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1993","unstructured":"Ketan Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, N.J., 1993."},{"key":"35_CR16","unstructured":"Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, 1992."},{"key":"35_CR17","unstructured":"Joseph O'Rourke. Computational Geometry in C. Cambridge University Press, 1994."},{"key":"35_CR18","unstructured":"T. K. Peucker, R. J. Fowler, J. J. Little, and D. M. Mark. The triangulated irregular network. In Amer. Soc. Photogrammetry Proc. Digital Terrain Models Symposium, pages 516\u2013532, 1978."},{"key":"35_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry-An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"Franco P. Preparata and Michael I. Shamos. Computational Geometry-An Introduction. Springer-Verlag, New York, 1985."},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 571\u2013575, 1996.","DOI":"10.1145\/237814.238005"},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"R. Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics, pages 37\u201368. Springer-Verlag, 1993.","DOI":"10.1007\/978-3-642-58043-7_3"},{"key":"35_CR22","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/B978-0-444-87806-9.50017-7","volume-title":"Computational Geometry","author":"R. Seidel","year":"1985","unstructured":"Raimund Seidel. A method for proving lower bounds for certain geometric problems. In Godfried T. Toussaint, editor, Computational Geometry, pages 319\u2013334. North Holland, Amsterdam, 1985."},{"key":"35_CR23","doi-asserted-by":"crossref","unstructured":"Cao An Wang and Francis Chin. Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time. In Paul Spirakis, editor, Algorithms-ESA'95, number 979 in Lecture Notes in Computer Science, pages 280\u2013294. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60313-1_150"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63397-9_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:18:01Z","timestamp":1559002681000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63397-9_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633976","9783540695363"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-63397-9_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}