an example program which documents the structures in libvor.a
libvor.a--written by Seth Teller (no relation to the destructively obsessed Edward T.) formally an sgi-gaud, who now spends his time at mit--is a 2D voronoi partition/delaunay triangulation/convex hull library based on Steve Fortune's plane sweep algorithm published in Algorithmica, 1987, "A Sweepline Algorithm for `Voronoi' Diagrams", volume 2, pp. 153-174, and Fortune's C code which resides on netlib. Its .h file, vordefs.h, and an example program, vorexamp.c, are included in this directory -- along with the requisite Makefile -- to better document the structures defined/accessed in ../lib/libvor.a.
our latest intelligence indicates that seth's current coords are:
a brief explanation:
Voronoi / Dirichlet / Wigner-Seitz regions are various names that a single mathematical object has come to be given. the object is defined by a set of "sites" in any dimension, as follows: partition space into regions, one per site, so that within each region every point is closer to its associated site than to any other site (at least as close to, on region boundaries).
the "dual" of this object, in any dimension, is the "delaunay triangulation" or tetrahedralization, a triangulation of space with the property that the circumsphere of every triangle has no sites in its interior.
that's all there is to it. both objects are very useful in diverse areas such as finite element modeling, image processing, computational geometry . . .
the package libvor.a uses steve fortune's algorithm to compute the voronoi diagram, delaunay triangulation, and convex hull in two dimensions.
for more background, read the excellent text, Computational Geometry: an Introduction, by Michael Ian Shamos and Franco P. Preparata, Springer-Verlag, 1985.
OR, ...