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

Sat Mar 24 10:48:29 PST 2001

```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)

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
http://www.geom.umn.edu/software/qhull/html/qhalf.htm
N-dimensional point distributions:
http://www.geom.umn.edu/software/qhull/html/rbox.htm