Higher Order Voronoi Diagrams


Justin Polchlopek
University of Utah

Overview

This program computes higher-order voronoi and delaunay triangulations. What is a higher-order voronoi diagram (HOVD)? To answer this question, we consider the definition of the (first order) voronoi diagram. Consider a set of points S on the plane (this generalizes to higher dimensions as well). The voronoi diagram of S is a decomposition of space into convex polygonal cells (polyhedral cells in higher dimensions). Each point x in S is associated to a cell that contains all the points in the plane that are closer to x than any other point in S. This cell complex is the nearest neighbor decomposition.

The HOVD extends the concept of the voronoi diagram by defining cells using the n nearest neighbors. For example, if x and y are distinct elements of S, then there is a (possibly empty) set of points defining a cell in the second order voronoi diagram. The nearest and second nearest neighbors of any point in this cell are x and y. The number of points of S that define a cell is the order of the HOVD.

A HOVD (which includes the first order VD) is a cell complex that subdivides space. However, unlike the first order VD, the dual to an HOVD (the Higher Order Delaunay Triangulation, or HODT), does not necessarily subdivide space. It is often the case that triangles of the HODT will have a non-empty intersection.

Methodology

Our program is built around an algorithm introduced by Boissonat, et al in Algorithmica 1993. This algorithm builds a k-Delaunay tree and uses it to allow for reasonably fast point insertion. By limiting the maximum order of the HODTs represented by this tree, point insertion can be kept to logarithmic time rather than the quadratic worst case.

We build the HODTs and extract the HOVDs from them. In building these triangulations, we must deal with finite and infinite triangles. The paper does an exceedingly poor job describing how to handle infinite triangles in that it doesn't explain it at all. But, I have determined how to handle the infinite triangle cases, and therefore, there are no restrictions on the point sets this program can handle. If you'd like information, and can't figure it out from the source, please contact me.

Problems and Future Plans

Our program currently does not limit the order of the voronoi diagrams it creates so point insertion slows down noticably as more points are added. We intend to slightly modify the algorithm to limit the order of the diagrams it produces.

This algorithm does not deal well with degeneracy! We get around this problem by perturbing input points slightly. We can do this since our program operates at pixel resolution, giving us the luxury of sliding points around inside the pixel they were located. In the future we would like to look into using Jonathan Shewchuk's robust predicate package to handle degeneracy, as well as to see what happens to higher order VDs and DTs near degeneracies.

Notes

We wrote this package to use doxygen. Calling make docs from the command line will build the documentation for the package. Be sure to edit .doxygen to correctly specify the path for the documentation.

Support

The source code in this distribution is written in C/C++ using GLUT and Paul Rademacher's GLUI libraries for Linux. It has been compiled for Windows, but I cannot guarantee the correctness of the Windows code, nor do I support creating the necessary project files for building it with any compiler other than GCC.

Licence

This package is distributed under the terms and conditions given by the LGPL.

	HOV: A Program for higher order voronoi diagrams
	Copyright (C) 2003 Justin Polchlopek

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public
	License along with this library; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

	Justin Polchlopek
	School of Computing
	50 S. Central Campus Drive
	Room 3190 MEB
	Salt Lake City, Utah 84112 

	Phone: 801 581 5642
	Fax: 801 581 5843

Download

The source distribution may be downloaded from http://www.cs.utah.edu/~justin/Wares/HOV.zip.

References

J.-D. Boissonnat, O. Devillers, and M. Teillaud.
A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis.
Algorithmica, 9:329--356, 1993