On bisectors for different distance functions

Let gamma (c) and gamma (D) be two convex distance functions in the plane w ith convex unit balls C and D. Given two points, p and q, we investigate th e bisector, B(p,q), of p and q, where distance from p is measured by gamma (C) and distance from q by gamma (D). We provide the following results. B(p ,q) may consist of many connected components whose precise number can be de rived from the intersection of the unit balls, C and D. The bisector can co ntain bounded or unbounded two-dimensional areas. Even more surprising, pie ces of the bisector may appear inside the region of all points closer to p than to q. If C and D are convex polygons over m and n vertices, respective ly, the bisector B(p, q) can consist of at most min(m, n) connected compone nts which contain at most 2(m + n) vertices altogether. The former bound is tight, the latter is tight up to an additive constant. We also present an optimal O(m + n) time algorithm for computing the bisector. (C) 2001 Elsevi er Science B.V. All rights reserved.