Voronoi Diagram

with the Minkowski Metric Lp

 

The Minkowski (power) metric from a point p to a point pi in Rm is defined by

 

dLp(p, pi) = [j=1∑m | xj - xij |p]1/p  --------------- 1

 

where (x1, x2, . . . , xm) and (xi1, xi2, . . . , xim) are the Cartesian coordinates of p and pi, respectively. Customarily the symbol Lp is used for the Minkowski metric, where p refers to the degree of the power.

 

The parameter p varies in the range of 1 ≤ p < ∞.

  1.  If p = 1, equation 1 becomes

     

    dL1(p, pi) = j=1∑m | xj - xij |       --------------- 2

     

    which is called the Manhattan metric, the city-block distance or the taxi-cab distance.

     

  2. If p = 2,  equation 1 becomes

    3.  

    dL2(p, pi) = [j=1∑m | xj - xij |2]1/2    

     

    which is called the Euclidean distance.

     

  3. If p = ∞, the equation 1 becomes

    4.  

    dL∞(p, pi) = [maxj { | xj - xij | j in Im }

     

    which is called the Supermum metric or dominance metric.