The limit of L_p Voronoi diagrams as p → 0 is the bounding-box-area Voronoi diagram

07/15/2022
by   Herman Haverkort, et al.
0

We consider the Voronoi diagram of points in the real plane when the distance between two points a and b is given by L_p(a-b) where L_p((x,y)) = (|x|^p+|y|^p)^1/p. We prove that the Voronoi diagram has a limit as p converges to zero from above or from below: it is the diagram that corresponds to the distance function L_*((x,y)) = |xy|. In this diagram, the bisector of two points in general position consists of a line and two branches of a hyperbola that split the plane into three faces per point. We propose to name L_* as defined above the "geometric L_0 distance".

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset