Animating a continuous family of two-site Voronoi diagrams (and a proof of a bound on the number of regions)

ABSTRACT

A two-site distance function defines a "distance" measure from a point to a pair of points; mathematically, it is a mapping D:R2×(R2×R2)R+. A Voronoi diagram for a two-site distance function D and a set S of planar point sites has a region V (p, q) for each pair of sites p,q-S , where V(p,q) is defined as the set of all points in the plane "closer" to (p, q)"under distance function D"than to any other pair of sites in S. Two-site distance functions and their Voronoi diagrams have been explored by Barequet et al. (2002) and animated by Barequet et al. (2001), who give

the complexity of the Voronoi diagram for the two-site sum function (among others), and leave as an open question the complexity of the diagram for the two-site perimeter function. In this video, we introduce and animate a new continuous family of two-site distance functions Dc defined for any constant ce-1. This family includes both the sum and perimeter distance functions, providing a unifying model. We also present and animate in this video a new proof that the perimeter function Voronoi diagram has O(n) non-empty regions. The proof generalizes to any function in the Dc family when ce0. The animation also shows how the various functions in the family relate to one another.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: Gill Barequet , Matthew T. Dickerson , Robert L. Scot Drysdale, 2-Point site Voronoi diagrams, Discrete Applied Mathematics, v.122 n.1-3, p.37-54, 15 October 2002 [doi>10.1016/S0166-218X(01)00320-1]
• 3: Gill Barequet , Robert L. Scot , Matthew T. Dickerson , David S. Guertin, 2-point site Voronoi diagrams, Proceedings of the seventeenth annual symposium on Computational geometry, p.323-324, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378723]
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
Voronoi diagrams, animation, complexity, two-site distance functions