{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T12:07:11Z","timestamp":1753358831980},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,1]]},"DOI":"10.1007\/bf02523236","type":"journal-article","created":{"date-parts":[[2006,11,7]],"date-time":"2006-11-07T23:39:46Z","timestamp":1162942786000},"page":"19-32","source":"Crossref","is-referenced-by-count":19,"title":["\u201cThe big sweep\u201d: On the power of the wavefront approach to Voronoi diagrams"],"prefix":"10.1007","volume":"17","author":[{"given":"F.","family":"Dehne","sequence":"first","affiliation":[]},{"given":"R.","family":"Klein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02523236_CR1","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","volume":"11","author":"M. Atallah","year":"1985","unstructured":"M. Atallah. Dynamic computational geometry.Comput. Math. Appl. 11, 1171\u20131181, 1985.","journal-title":"Comput. Math. Appl."},{"issue":"3","key":"BF02523236_CR2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"F. Aurenhammer. Voronoi diagrams\u2014a survey of a fundamental data structure.ACM Comput. Surveys 23 (3), 345\u2013405, 1991.","journal-title":"ACM Comput. Surveys"},{"issue":"5","key":"BF02523236_CR3","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(79)90074-7","volume":"9","author":"K. Q. Brown","year":"1979","unstructured":"K. Q. Brown. Voronoi diagrams from convex hulls.Inform. Process. Lett. 9 (5), 223\u2013228, 1979.","journal-title":"Inform. Process. Lett."},{"key":"BF02523236_CR4","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. 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."},{"key":"BF02523236_CR5","doi-asserted-by":"crossref","unstructured":"L. P. Chew and R. L. Drysdale III. Voronoi diagrams based on convex distance functions.Proceedings of the 1st ACM Symposium on Computational Geometry, 1985, 235\u2013244.","DOI":"10.1145\/323233.323264"},{"key":"BF02523236_CR6","unstructured":"R. Cole. Reported by C. \u00d3'D\u00fanlaing, 1989."},{"key":"BF02523236_CR7","series-title":"Staffelstein. LNCS","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/3-540-19422-3_5","volume-title":"Graphtheoretic Concepts in Computer Science (WG '87)","author":"F. Dehne","year":"1988","unstructured":"F. Dehne and R. Klein. A sweepcircle algorithm for Voronoi diagrams. In H. G\u00f6ttler and H. J. Schneider, editors,Graphtheoretic Concepts in Computer Science (WG '87), pp. 59\u201370, Staffelstein. LNCS 314, Springer-Verlag, Berlin, 1988."},{"key":"BF02523236_CR8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements.Discrete Comput. Geom. 1, 25\u201344, 1986.","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"BF02523236_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune. A sweepline algorithm for Voronoi diagrams.Algorithmica 2 (2), 153\u2013174, 1987.","journal-title":"Algorithmica"},{"key":"BF02523236_CR10","doi-asserted-by":"crossref","unstructured":"Ch. Icking, R. Klein, N.-M. Le, and L. Ma. Convex distance functions in 3D are different,Proceedings of the 9th ACM Symposium on Computational Geometry, 1993, pp. 116\u2013123.","DOI":"10.1145\/160985.161007"},{"key":"BF02523236_CR11","series-title":"W\u00fcrzburg. LNCS","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/3-540-50335-8_31","volume-title":"Computational Geometry and Its Applications (CG '88)","author":"R. Klein","year":"1988","unstructured":"R. Klein. Abstract Voronoi diagrams and their applications. In H. Noltemeier, editor,Computational Geometry and Its Applications (CG '88), pp. 148\u2013157, W\u00fcrzburg. LNCS 333, Springer-Verlag, Berlin, 1988."},{"key":"BF02523236_CR12","series-title":"LNCS","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi diagrams","author":"R. Klein","year":"1989","unstructured":"R. Klein.Concrete and Abstract Voronoi diagrams. LNCS 400, Springer-Verlag, Berlin, 1989."},{"key":"BF02523236_CR13","series-title":"Tokyo. LNCS","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/3-540-52921-7_63","volume-title":"Algorithms (SIGAL '90)","author":"R. Klein","year":"1990","unstructured":"R. Klein, K. Mehlhorn, and St. Meiser On the construction of abstract Voronoi diagrams, II. In T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki, editors,Algorithms (SIGAL '90), pp. 138\u2013154, Tokyo. LNCS 450, Springer-Verlag, Berlin, 1990."},{"key":"BF02523236_CR14","series-title":"Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS '88)","first-page":"281","volume-title":"Voronoi diagrams based on general metrics in the plane","author":"R. Klein","year":"1988","unstructured":"R. Klein and D. Wood. Voronoi diagrams based on general metrics in the plane.Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS '88), pp. 281\u2013291, Bordeaux. LNCS 294, Springer-Verlag, Berlin, 1988."},{"key":"BF02523236_CR15","volume-title":"Voronoi diagrams based on strictly convex distances on the plane","author":"M. L. Maz\u00f3n","year":"1991","unstructured":"M. L. Maz\u00f3n and T. Recio. Voronoi diagrams based on strictly convex distances on the plane. Manuscript, Departamento De Matem\u00e1ticas, Universidad de Cantabria, Santander, 1991."},{"key":"BF02523236_CR16","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02574686","volume":"6","author":"K. Mehlhorn","year":"1991","unstructured":"K. Mehlhorn, St. Meiser, and C. O'D\u00fanlaing. On the construction of abstract Voronoi diagrams.Discrete Comput. Geom. 6, 211\u2013224, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523236_CR17","unstructured":"R. Seidel. Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles. Technical Report 260, IIG-TU Graz, pages 178\u2013191, 1988."},{"key":"BF02523236_CR18","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey. Closest-point problems.Proceedings of the 16th IEEE Symposium on Foundations of Computer Science, 1975, pp. 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF02523236_CR19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF01759042","volume":"6","author":"G. M. Shute","year":"1991","unstructured":"G. M. Shute, L. L. Deneen, and C. D. Thomborson. AnO(n logn) plane-sweep algorithm forL 1 andL \u221e Delaunay triangulations,Algorithmica 6, 207\u2013221, 1991.","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523236.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523236\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:39:41Z","timestamp":1558283981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["BF02523236"],"URL":"https:\/\/doi.org\/10.1007\/bf02523236","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}