Abstract
Given a set of non-intersecting (except at endpoints) line segments in the plane we want to compute their Voronoi diagram. Although there are several algorithms for this problem in the literature [Yap87, For87, CS89, BDS+92, KMM90] nobody claims to have a correct implementation. This is due to the fact that the algorithms presuppose exact arithmetic and that the Voronoi diagram of segments requires to compute with non-rational algebraic numbers. We report about a detailed study of the numerical precision required for evaluating the geometric test exactly and about first experimental experiences. More specifically, we improve the precision bound implied by classical root separation results by more than two orders of magnitude and we compare the implementation strategies suggested by our theoretical results.
Preview
Unable to display preview. Download preview PDF.
References
F. Aurenhammer. Voronoi diagrams: a survey of a fundamental geometric data structure. ACM Comput. Surv., 23:345–405, 1991.
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.
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–71, 1992.
M.O. Benouamer, P. Jaillon, D. Michelucci, and J-M. Moreau. A “lazy” solution to imprecision in computational geometry. In 5th Canadian Conf. on Computational Geometry, pages 73–78, 1993.
J. Blömer. Computing sums of radicals in polynomial time. In FOCS91, pages 670–677, 1991.
J. Blömer. Computing sums of radicals in polynomial time. Technical Report B93-13, Freie Universität Berlin, 1993.
B. Butz. Robuste Implementierung eines Algorithmus zur Berechung eines Voronoi-Diagrams für Polygone. Diplomarbeit, 1994.
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete and Computational Geometry, pages 387–421, 1989.
T. Dube and C.K. Yap. A basis for implementing exact computational geometry. extended abstract, 1994.
S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153–174, 1987.
S. Fortune. Numerical stability of algorithms for 2d Delaunay triangulations and Voronoi diagrams. In ACM Symposium on Computational Geometry, volume 8, pages 83–92, 1992.
S. Fortune and C. van Wyk. Efficient exact arithmetic for computational geometry. Proc. of the 9th Symp. on Computational Geometry, pages 163–171, 1993.
S. Fortune and C. van Wyk. Efficient exact arithmetic for computational geometry. In Proc. of the 9th ACM Symp. on Computational Geometry, pages 163–172, 1993.
M. Karasick, D. Lieber, and L.R. Nackman. Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics, 10(1):71–91, 1991.
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.
Z. Li and V. Milenkovic. Constructing strongly convex hulls using exact or rounded arithmetic. Algorithmica, 8:345–364, 1992.
R. Loos. Computing in algebraic extensions. In B. Buchberger, G.E. Collins, and R. Loos, editors, Computer Algebra, pages 173–187. Springer Verlag, 1982.
M. Mignotte. Mathematics for Computer Algebra. Springer Verlag, 1992.
K. Mehlhorn and S. Näher. Implementation of a sweep line algorithm for the segment intersection problem. manuscript.
A. Okabe, B. Boots, and Sugihara, K. Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley, New York, 1992.
T. Ottmann, G. Thiemt, and C. Ullrich. Numerical stability of geometric algorithms. In Proc. of the 3rd ACM Symp. on Computational Geometry, pages 119–125, 1987.
C. O'Dúnlaing and C. Yap. A “retraction” method for planning the motion of a disk. Journal of Algorithms, 6:104–111, 1985.
M. Seel. Ausarbeitung und Implementierung eines Algorithmus zur Konstruktion abstrakter Voronoi-Diagramme. Diplomarbeit, 1994.
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–39, 1990.
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–393, 1987.
C.K. Yap. Towards exact geometric computation. In 5th Canadian Conf. on Computational Geometry, pages 405–419, 1993.
C.K. Yap. Fundamental Problems in Algorithmic Algebra. Princeton University Press, 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Burnikel, C., Mehlhorn, K., Schirra, S. (1994). How to compute the Voronoi diagram of line segments: Theoretical and experimental results. In: van Leeuwen, J. (eds) Algorithms — ESA '94. ESA 1994. Lecture Notes in Computer Science, vol 855. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0049411
Download citation
DOI: https://doi.org/10.1007/BFb0049411
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58434-6
Online ISBN: 978-3-540-48794-4
eBook Packages: Springer Book Archive