Site Tools


l0-distance

The Geometric L0-Distance

Suppose S is a finite set of points in the plane, and the distance between two points s and q in the plane is measured by the Lp distance Lp(sq), where Lp( (x,y) ) = (|x|p+|y|p)1/ p. What happens to the Voronoi diagram of S if p gets close to zero? Surprisingly, although for p close to zero, Lp and L−p have very different values, they induce almost the same Voronoi diagram. In fact, as p approaches zero from above or from below, the Voronoi diagram converges to the Voronoi diagram of the distance function L*( (x,y) ) = |xy|. The proof can be found in the following paper:

  • The limit of Lp Voronoi diagrams as p→0 is the bounding-box-area Voronoi diagram.
    By Herman Haverkort and Rolf Klein.
    Computing Research Repository (arXiv.org), 2207.07377, 2022.
    text; GeoGebra worksheet

Therefore we propose to define the geometric L0 distance by L0( (x,y) ) = |xy|. Thus, we have the following special cases of the (geometric) Lp distance:

L−∞( (x, y) ) = min( |x|, |y| )
L0( (x, y) ) = product( |x|, |y| ) (not to be confused with other definitions!)
L1( (x, y) ) = sum( |x|, |y| ) (Manhattan metric)
L2( (x, y) ) = √( |x|² + |y|² ) (Euclidean metric)
L( (x, y) ) = max( |x|, |y| )

l0-distance.txt · Last modified: 2022/07/18 07:33 by administrator