2000 : The 5th Revision Thursday, 03-Jun-2010 22:12:25 JST)

Voronoi diagrams (Automatic version)	Ordinary	Multiplicatively Weighted /Area	Additively W /Area	PW(additively Weighted Power)	Compoundly W	LW(L_{weight} norm)
Higher-order	HMW	HAW	HPW	HCW	HLW
Elliptic	Manhattan	Supremum	Karlsruhe	Farthest-point
HElliptic	HManhattan Farthest-Point Manhattan	HSupremum	HKarlsruhe	Higher-order Farthest-point
line-segment	line-segments sometimes cross each other	line-segments need to cross each other	largest empty circle in a polygon
Higher order line-segment	Higher order line-segment (segnebts sometimes cross each other)	Higher order line-segment (segments need to cross each other)
Area of Voronoi Region /MW Area /AW Area	Delaunay Tessellation	order-2 Delaunay	Order-3 Delaunay	Farthest Delaunay
Delaunay some edges deleted	-	-	Extended Voronoi Edges	-	-
Voronoi area game for two	for three	for four	for five	for six	-
Voronoi diagrams (Click version)	Ordinary	-	Largest Empty circle in a polygon
Higher-order
-	Manhattan	Supremum	Karlsruhe	Farthest-point
HManhattan Farthest-Point Manhattan	HSupremum	HKarlsruhe
Area of Voronoi Region	Delaunay Tessellation	order-2 Delaunay	Order-3 Delaunay	Farthest Delaunay
Voronoi area game for two	for three	for four	for five	for six	-

If we use Higher order Voronoi diagram, we can find out the 2nd or 3rd nearest facility.
White is the first order, green is 2nd, and blue is 3rd.
Algorithm for the higher order Voronoi diagrams (If you want draw the l-th order Voronoi diagram, then m=1,2,...,l)

i=1,...,N-1
    j=i+1,...,N
        Consider a bisector of p(i) and p(j)
        k=1,...,N except for i and j
            Consider a bisector of p(i) and p(k)
            Calculate points of intersection of bisector(i,j) and bisector(i,k)
        next k
        Add the points at x=0 and x=(the width of the screen) of the bisector of i and j into points of intersections
        Sort points of intersections in turns of x coordinates
        k=1,...,the number of interval of points of intersections
            Let c be a middle point of interval of points of intersection
            Let d be d(c,p(i))
            label=0
            h=1,...,N except for i and j
                Let d' be d(c,p(h))
                If d'<d then label=label+1
            next h
            If label=m-1, then draw the interval of points of intersection by m-th order's color.
         next k
    next j
next i

And the following is the algorithm of the ordinary Voronoi diagram. It is very similar.

i=1,...,N-1
    j=i+1,...,N
        Consider a bisector of p(i) and p(j)
        k=1,...,N except for i and j
            Consider a bisector of p(i) and p(k)
            Calculate points of intersection of bisector(i,j) and bisector(i,k)
        next k
        Add the points at x=0 and x=(the width of the screen) of the bisector of i and j into points of intersections
        Sort points of intersections in turns of x coordinates
        k=1,...,the number of interval of points of intersections
            Let c be a middle point of interval of points of intersection
            Let d be d(c,p(i))
            label=0
            h=1,...,N except for i and j
                Let d' be d(c,p(h))
                If d'<d then label=1
            next h
            If label=0, then draw the interval of points of intersection
         next k
    next j
next i

Java(hivoro.java)

If you have a message, don't hesitate to send it by using
E-mail:

Mail Form
or
BBS

Use of Takashi Ohyama's website
English Home of Takashi Ohyama
Japanese Home of Takashi Ohyama