CONVEX DISTANCE FUNCTIONS IN 3-SPACE ARE DIFFERENT

Article type: Research Article

Authors: Icking, Christian | Klein, Rolf | Lé, Ngoc-Minh | Ma, Lihong

Affiliations: Fern Universität Hagen, Praktische Informatik VI, Elberfelder Str. 95, D-58084 Hagen, Germany

Abstract: The bisector systems of convex distance functions in 3-space are investigated and it is shown that there is a substantial difference to the Euclidean metric which cannot be observed in 2-space. This disproves the general belief that Voronoi diagrams in convex distance functions are, in any dimension, analogous to Euclidean Voronoi diagrams. The fact is that more spheres than one can pass through four points in general position. In the L4-metric, there exist quadrupels of points that lie on the surface of three L4-spheres. Moreover, for each n ≥ 0 one can construct a smooth and symmetric convex distance function d and four points that are contained in the surface of exactly 2n+1+ d-spheres, and this number does not decrease if the four points are disturbed independently within 3-dimensional neighborhoods. This result implies that there is no general upper bound to the complexity of the Voronoi diagram of four sites based on a convex distance function in 3-space.

Keywords: Convex distance functions, Voronoi diagrams

DOI: 10.3233/FI-1995-2242

Journal: Fundamenta Informaticae, vol. 22, no. 4, pp. 331-352, 1995