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
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.

This program will compute the order voronoi diagram. It is a quick
and, I hope, not so dirty implementation. It uses an 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 algorithm to do so.

I wrote C code for this many years ago. I chose the 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.