{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T18:38:44Z","timestamp":1784918324590,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540584346","type":"print"},{"value":"9783540487944","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049411","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:42:35Z","timestamp":1141670555000},"page":"227-239","source":"Crossref","is-referenced-by-count":19,"title":["How to compute the Voronoi diagram of line segments: Theoretical and experimental results"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Burnikel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Schirra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"F. Aurenhammer. Voronoi diagrams: a survey of a fundamental geometric data structure. ACM Comput. Surv., 23:345\u2013405, 1991.","journal-title":"ACM Comput. Surv."},{"key":"21_CR2","unstructured":"J.D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Technical report, INRIA, 1990."},{"key":"21_CR3","doi-asserted-by":"crossref","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 and Computational Geometry, 8:51\u201371, 1992.","journal-title":"Discrete and Computational Geometry"},{"key":"21_CR4","unstructured":"M.O. Benouamer, P. Jaillon, D. Michelucci, and J-M. Moreau. A \u201clazy\u201d solution to imprecision in computational geometry. In 5th Canadian Conf. on Computational Geometry, pages 73\u201378, 1993."},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"J. Bl\u00f6mer. Computing sums of radicals in polynomial time. In FOCS91, pages 670\u2013677, 1991.","DOI":"10.1109\/SFCS.1991.185434"},{"key":"21_CR6","volume-title":"Technical Report B93-13","author":"J. Bl\u00f6mer","year":"1993","unstructured":"J. Bl\u00f6mer. Computing sums of radicals in polynomial time. Technical Report B93-13, Freie Universit\u00e4t Berlin, 1993."},{"key":"21_CR7","unstructured":"B. Butz. Robuste Implementierung eines Algorithmus zur Berechung eines Voronoi-Diagrams f\u00fcr Polygone. Diplomarbeit, 1994."},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete and Computational Geometry, pages 387\u2013421, 1989.","DOI":"10.1007\/BF02187740"},{"key":"21_CR9","unstructured":"T. Dube and C.K. Yap. A basis for implementing exact computational geometry. extended abstract, 1994."},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. J. Fortune","year":"1987","unstructured":"S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153\u2013174, 1987.","journal-title":"Algorithmica"},{"key":"21_CR11","first-page":"83","volume":"8","author":"S. Fortune","year":"1992","unstructured":"S. Fortune. Numerical stability of algorithms for 2d Delaunay triangulations and Voronoi diagrams. In ACM Symposium on Computational Geometry, volume 8, pages 83\u201392, 1992.","journal-title":"ACM Symposium on Computational Geometry"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"S. Fortune and C. van Wyk. Efficient exact arithmetic for computational geometry. Proc. of the 9th Symp. on Computational Geometry, pages 163\u2013171, 1993.","DOI":"10.1145\/160985.161015"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"S. Fortune and C. van Wyk. Efficient exact arithmetic for computational geometry. In Proc. of the 9th ACM Symp. on Computational Geometry, pages 163\u2013172, 1993.","DOI":"10.1145\/160985.161015"},{"issue":"1","key":"21_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/99902.99905","volume":"10","author":"M. Karasick","year":"1991","unstructured":"M. Karasick, D. Lieber, and L.R. Nackman. Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics, 10(1):71\u201391, 1991.","journal-title":"ACM Transactions on Graphics"},{"key":"21_CR15","volume-title":"LNCS 450","author":"R. Klein","year":"1990","unstructured":"R. Klein, K. Mehlhorn, and S. Meiser. On the construction of abstract Voronoi diagrams ii. In Proc. SIGAL Symp. on Algorithms, Tokyo, 1990. Springer Verlag. LNCS 450."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF01758851","volume":"8","author":"Z. Li","year":"1992","unstructured":"Z. Li and V. Milenkovic. Constructing strongly convex hulls using exact or rounded arithmetic. Algorithmica, 8:345\u2013364, 1992.","journal-title":"Algorithmica"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"R. Loos. Computing in algebraic extensions. In B. Buchberger, G.E. Collins, and R. Loos, editors, Computer Algebra, pages 173\u2013187. Springer Verlag, 1982.","DOI":"10.1007\/978-3-7091-3406-1_12"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"M. Mignotte. Mathematics for Computer Algebra. Springer Verlag, 1992.","DOI":"10.1007\/978-1-4613-9171-5"},{"key":"21_CR19","unstructured":"K. Mehlhorn and S. N\u00e4her. Implementation of a sweep line algorithm for the segment intersection problem. manuscript."},{"key":"21_CR20","volume-title":"Spatial tessellations: concepts and applications of Voronoi diagrams","author":"A. Okabe","year":"1992","unstructured":"A. Okabe, B. Boots, and Sugihara, K. Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley, New York, 1992."},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"T. Ottmann, G. Thiemt, and C. Ullrich. Numerical stability of geometric algorithms. In Proc. of the 3rd ACM Symp. on Computational Geometry, pages 119\u2013125, 1987.","DOI":"10.1145\/41958.41970"},{"key":"21_CR22","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/0196-6774(85)90021-5","volume":"6","author":"C. O'D\u00fanlaing","year":"1985","unstructured":"C. O'D\u00fanlaing and C. Yap. A \u201cretraction\u201d method for planning the motion of a disk. Journal of Algorithms, 6:104\u2013111, 1985.","journal-title":"Journal of Algorithms"},{"key":"21_CR23","unstructured":"M. Seel. Ausarbeitung und Implementierung eines Algorithmus zur Konstruktion abstrakter Voronoi-Diagramme. Diplomarbeit, 1994."},{"key":"21_CR24","unstructured":"K. Sugihara, Y. Ooishi, and T. Imai. Topology-oriented approach to robustness and its applications to several Voronoi-diagram algorithms. In Proc. 2nd Canad. Conf. Comput. Geom., pages 36\u201339, 1990."},{"key":"21_CR25","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02187890","volume":"2","author":"C. Yap","year":"1987","unstructured":"C. Yap. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete and Computational Geometry, 2:365\u2013393, 1987.","journal-title":"Discrete and Computational Geometry"},{"key":"21_CR26","unstructured":"C.K. Yap. Towards exact geometric computation. In 5th Canadian Conf. on Computational Geometry, pages 405\u2013419, 1993."},{"key":"21_CR27","unstructured":"C.K. Yap. Fundamental Problems in Algorithmic Algebra. Princeton University Press, 1994."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049411","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T23:00:17Z","timestamp":1736290817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049411"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0049411","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}