Higher Order Voronoi Diagrams: A Java Applet

What is a Voronoi diagram? What is an order K Voronoi diagram? Let S be a set of n sites in the Euclidean plane. Informally, the Voronoi diagram is a subdivision of the plane into regions such that each point of a region has the same closest site. There are many variants, including the tex2html_wrap_inline26 order Voronoi diagram, which is a partition of the plane into regions such that points in each region have the same k closest sites.

Here is a simple applet that allows you to click to add sites, and then compute a Voronoi diagram of any order.


Your previewer must be able to run java to run this applet.

This program will compute the tex2html_wrap_inline26 order voronoi diagram. It is a quick and, I hope, not so dirty implementation. It uses an tex2html_wrap_inline32 algorithm, so it is useful only for a small number of points. The algorithm is described in a paper by Frank Dehne called ``An optimal algorithm to construct all Voronoi diagrams for k nearest neighbor searching in the euclidean plane''. Note: This algorithm is not optimal; there is an tex2html_wrap_inline34 algorithm to do so.
I wrote C code for this many years ago. I chose the tex2html_wrap_inline32 algorithm because it was easy to implement (A few days at most, including an X Windows interface). In January 1997, I decided it was time to learn Java - This is my first Java program. I wanted to write a substantial (but not too substantial) java program to get to know the entire language. This algorithm seemed ideal: It used many concepts, such as linked lists, a user interface, and I could modify existing code, rather than start from scratch. It took about 3 days to translate the C code to java, while learning java.

Note: When sites are added, the coordinates printed to the java console.

Known Bug: Parallel lines. If the perpendicular bisectors of three sites are parallel, then either these lines may not be drawn, or there is a NullPointerException. I probably won't get around to fixing this. Avoid 3 colinear sites.