Automatic version | Center problem | Empty circle, Largest empty circle | Largest empty ellipse |
---|---|---|---|

Click version | Center problem | Empty circle, Largest empty circle | - |

Farthest point Voronoi diagram(Automatic version)EFarthest point Voronoi diagram(Click version)

Elliptic Voronoi diagram(Automatic version)

If we use Farthest-point Voronoi diagram, we can find out the farthest facility.

Algorithm

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 the points of intersection of bisector(i,j) and bisector(i,k) next k Add the points x=0 and x=(the width of screen) of the bisector (i,j) into the points of intersections Sort the points of intersections in terms of x coordinates k=1,...,the number of intervals of the points of intersections Let c be a midpoint of the interval of the points of intersection. Let d be d(c,p(i)) cnt=0 h=1,...,N except for i and j Let d' be d(c,p(h)) If d'<d then shout cnt=cnt+1 next h If cnt=N-2, then draw the interval of the points of intersection next k next j next i

Java(fpvoro.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