Convex distance functions in 3-space are different

Publisher Website
Google Scholar
Abstract
The bisector systems of convex distance functions in 3-space are investigated and it is shown that there is a substantial dierence 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 ,a nd 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

This publication has 0 references indexed in Scilit: