On the Triangle-Perimeter Two-Site Voronoi Diagram
Iddo Hanniel, Gill Barequet · 2009
The triangle-perimeter 2-site distance function defines the "distance" P(x, (p, q)) from a point x to two other points p, q as the perimeter of the triangle whose vertices are x, p, q. Accordingly, given a set S of n points in the plane, the Voronoi diagram of S with respect to P, denoted as VP(S), is the subdivision of the plane into regions, where the region of p, q ¿ S is the locus of all points closer to p, q (according to P) than to any other pair of sites in S. In this paper we prove a theorem about the perimeters of triangles, two of whose vertices are on a given circle. We use this theorem to show that the combinatorial complexity of VP(S) is O(n2+¿) (for any ¿ > 0). Consequently, we show that one can compute VP(S) on O(n2+¿) time and space.