University of Utah

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.

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.

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.

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.

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.

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

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

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