Announce: Qhull 3.0 for convex hull, Delaunay, Voronoi, Halfspace

[Brad Barber]

I am pleased to announce Qhull 3.0 for computing
convex hulls, Delaunay triangulations, Voronoi diagrams, and
halfspace intersection about a point.  It includes programs
for each of these structures.

Qhull uses floating point arithmetic to compute an approximation
to the convex hull.  Each facet is defined by an outer plane that
is clearly above all points and an inner plane that is clearly below
the vertices.  It provides two methods to handle precision errors:

   facet merging -- If a ridge is not clearly convex, Qhull merges
                           a facet into a neighboring facet.

   joggled input --  Qhull randomly perturbs the input.  If a precision
                           error occurs, Qhull restarts with a larger joggle.

For example,

      rbox 1000 W0 | qconvex QR0 R1e-3

computes the convex hull of 1000 points on the surface of a rotated
unit cube.  To test Qhull, each computation is randomly perturbed
by up to 0.001.   Qhull merged 92 facets to handle precision errors.

Convex hull of 1000 points in 3-d:

   Number of vertices: 52
   Number of facets: 39
   Number of non-simplicial facets: 12

Statistics for: RBOX 1000 W0 | QCONVEX QR0 R1e-3 QR985448492

   Number of points processed: 62
   Number of hyperplanes created: 178
   Number of distance tests for qhull: 18629
   Number of merged facets: 92
   Number of distance tests for merging: 2801
   CPU seconds to compute hull (after input): 0.11
   Maximum distance of point above facet: 0.0038 (0.6x)
   Maximum distance of vertex below facet: -0.0074 (1.2x)

Home page:
       http://www.geom.umn.edu/locate/qhull
Convex hull:
       http://www.geom.umn.edu/software/qhull/html/qconvex.htm
Delaunay triangulation:
       http://www.geom.umn.edu/software/qhull/html/qdelaun.htm
Voronoi diagram:
       http://www.geom.umn.edu/software/qhull/html/qvoronoi.htm
Halfspace intersection about a point:
       http://www.geom.umn.edu/software/qhull/html/qhalf.htm
N-dimensional point distributions:
       http://www.geom.umn.edu/software/qhull/html/rbox.htm

                                                                      --Brad


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.