On the Triangle-Perimeter Two-Site Voronoi Diagram

摘要

The triangle-perimeter 2-site distance function defines the "distance" from a point x to two other points p,qa& 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 the triangle-perimeter distance, is the subdivision of the plane into regions, where the region of the pair p, q € S is the locus of all points closer to p, q (according to the triangle-perimeter distance) 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 the triangle-perimeter 2-site Voronoi diagram is O(n2+￡) (for any e > 0). Consequently, we show that one can compute the diagram in O(n2+e) time and space.