Yet another algorithm for generalized Voronoï Diagrams

ABSTRACT

We design and implement an efficient algorithm for the computation of generalized Voronoï Diagrams (VD's) constrained to a given domain. Our framework is general and applicable to any VD-type where the distance field is given by a polynomial. We use the Bernstein form of polynomials to subdivide the domain and isolate bisector domains or domains that contain a Voronoï vertex. Efficiency is due to a filtering process, based on bounding the distance functions over the subdivided domains. The output is a polygonal description of each Voronoï cell up to any user-defined precision.

References

1. O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer, and M. Rabl. Divide-and-conquer algorithms for Voronoï diagrams revisited. Comput. Geom. Theory Appl., 43: 688--699, 2010.
2. H. Edelsbrunner and R. Seidel. Voronoï diagrams and arrangements. Discr. and Compt. Geom., 1: 25--44, 1986.
3. I. Z. Emiris, E. P. Tsigaridas, and G. M. Tzoumas. Exact Delaunay graph of smooth convex pseudo-circles: general predicates, and implementation for ellipses. In SPM '09, p. 211--222, NY, USA, 2009. ACM.
4. G. Farin. Curves and surfaces for CAGD: a practical guide. Morgan Kaufmann Publishers Inc., SF, CA, USA, 2002.
5. F. Labelle and J. R. Shewchuk. Anisotropic Voronoï diagrams and guaranteed-quality anisotropic mesh generation. In SCG '03, p. 191--200, NY, USA, 2003. ACM.
6. A. Mantzaflaris and B. Mourrain. A subdivision approach to planar semi-algebraic sets. In Geometric Modeling and Processing, vol. 6130 of LNCS, p. 104--123. Springer, 2010.
7. B. Mourrain and J. Pavone. Subdivision methods for solving polynomial equations. JSC, 44(3): 292--306, 2009.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis