{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:18:23Z","timestamp":1737091103398,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424932"},{"type":"electronic","value":"9783540446767"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_26","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T16:43:15Z","timestamp":1179506595000},"page":"312-320","source":"Crossref","is-referenced-by-count":0,"title":["Splitting a Delaunay Triangulation in Linear Time"],"prefix":"10.1007","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[]},{"given":"Olivier","family":"Devillers","sequence":"additional","affiliation":[]},{"given":"Ferran","family":"Hurtado","sequence":"additional","affiliation":[]},{"given":"Merc\u00e8","family":"Mora","sequence":"additional","affiliation":[]},{"given":"Vera","family":"Sacrist\u00e1n","sequence":"additional","affiliation":[]},{"given":"Monique","family":"Teillaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"issue":"6","key":"26_CR1","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom., 4(6):591\u2013604, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"N. M. Amato, M. T. Goodrich, and E. A. Ramos. Linear-time triangulation of a simple polygon made easier via randomization. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 201\u2013212, 2000.","DOI":"10.1145\/336154.336206"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/BF02293035","volume":"8","author":"J.-D. Boissonnat","year":"1992","unstructured":"J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete Comput. Geom., 8:51\u201371, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"J.-D. Boissonnat, O. Devillers, M. Teillaud, and M. Yvinec. Triangulations in CGAL. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 11\u201318, 2000.","DOI":"10.1145\/336154.336165"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(93)90024-N","volume":"112","author":"J.-D. Boissonnat","year":"1993","unstructured":"J.-D. Boissonnat and M. Teillaud. On the randomized construction of the Delaunay tree. Theoret. Comput. Sci., 112:339\u2013354, 1993.","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"26_CR6","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(5):485\u2013524, 1991.","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"26_CR7","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1137\/0221041","volume":"21","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle. An optimal algorithm for intersecting three-dimensional convex poly-hedra. SIAM J. Comput., 21(4):671\u2013696, 1992.","journal-title":"SIAM J. Comput."},{"key":"26_CR8","volume-title":"Technical Report PCS-TR90-147","author":"L. P. Chew","year":"1986","unstructured":"L. P. Chew. Building Voronoi diagrams for convex polygons in linear expected time. Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth College, Hanover, NH, 1986."},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF02526034","volume":"18","author":"L. P. Chew","year":"1997","unstructured":"L. P. Chew and S. Fortune. Sorting helps for Voronoi diagrams. Algorithmica, 18:217\u2013228, 1997.","journal-title":"Algorithmica"},{"issue":"3","key":"26_CR10","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/PL00009429","volume":"21","author":"F. Chin","year":"1999","unstructured":"F. Chin, J. Snoeyink, and C. A. Wang. Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom., 21(3):405\u2013420, 1999.","journal-title":"Discrete Comput. Geom."},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"L. Clarkson","year":"1989","unstructured":"L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387\u2013421, 1989.","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"26_CR12","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0020-0190(97)00125-7","volume":"63","author":"M. Berg","year":"1997","unstructured":"M. de Berg, O. Devillers, K. Dobrindt, and O. Schwarzkopf. Computing a single cell in the overlay of two simple polygons. Inform. Process. Lett., 63(4):215\u2013219, Aug. 1997.","journal-title":"Inform. Process. Lett."},{"key":"26_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"1997","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997."},{"issue":"1","key":"26_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1142\/S021819599200007X","volume":"2","author":"O. Devillers","year":"1992","unstructured":"O. Devillers. Randomization yields simple O(n log* n) algorithms for difficult \u03a9(n) problems. Internat. J. Comput. Geom. Appl., 2(1):97\u2013111, 1992.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1142\/S0218195995000192","volume":"5","author":"H. Djidjev","year":"1995","unstructured":"H. Djidjev and A. Lingas. On computing Voronoi diagrams for sorted point sets. Internat. J. Comput. Geom. Appl., 5:327\u2013337, 1995.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"26_CR16","doi-asserted-by":"publisher","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"},{"key":"26_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1142\/S0218195996000198","volume":"6","author":"R. Klein","year":"1996","unstructured":"R. Klein and A. Lingas. A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon. Internat. J. Comput. Geom. Appl., 6:263\u2013278, 1996.","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"1","key":"26_CR18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","volume":"1","author":"R. Seidel","year":"1991","unstructured":"R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):51\u201364, 1991.","journal-title":"Comput. Geom. Theory Appl."},{"key":"26_CR19","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"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T12:18:29Z","timestamp":1737029909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}