In general, the distance between two points can be given by a convex distance function d_C . A convex distance function can be defined in the following way. Let C be a compact, convex set in the plane containing the origin in the interior, which is called the center of C. To define the distance from p  to q with regard to C,  first the C is tranlated to p ; see figure.

The ray from p through q intersects the boundary of C at exact one point q'. We define

this amout gives exactly the factor, that the convex set C translated to p  must be expanded or contracted for the boundary of C to touch q. The function d_C fulfils d_C(p,q) >= 0 and d_C(p,q) = 0 iff p=q.  d_C fulfils also the triangle inequality

The symmetry condition d_C(p,q) = d_C(q,p) holds, if C is symmetric about the origin;  then d_C  is also a metric. A convex distance function is called smooth, if at each boundary point to C there exists an unique supporting line.  A convex distance function is strictly convex, if the boundary of C does not contain a segment.

Of course we can compute the bisectors and Voronoi diagrams determined by a convex distance function.

© 1997 FernUniversität Hagen, Praktische Informatik VI
© 2001 University of Bonn, Dept. of Computer Science I

© University of Bonn, Computer Science I - - Last modified 03-02-2005 15:17