Announce: Qhull 3.1 with triangulated output

[Brad Barber]

I've released Qhull 3.1 with triangulated output and improved
handling of difficult inputs.   Qhull computes convex hulls,
Delaunay triangulations, Voronoi diagrams, and halfspace
intersections about a point.
       http://www.geom.umn.edu/locate/qhull

Triangulated output triangulates non-simplicial facets.  Triangulated
output is more accurate than joggled input for Delaunay triangulations
and other applications.

I've identified an additional class of difficult inputs for Qhull.   The
following distributions have a few large facets and many small facets
that meet at a sharp angle.

- The Delaunay triangulation of 1000 nearly cospherical points
     (fixed with option 'Qbb'):

       rbox 1000 s W1e-13 t | qhull d Tv

- The Delaunay triangulation of 1000 nearly cocircular points
     plus the origin (option 'Qbb' would have little effect).

       rbox s 1000 W1e-13 P0 D2 t | qhull d Tv

-  The convex hull of 1001 cospherical points of which
      1000 are nearly cocircular.

       rbox 1000 s Z1 G1e-13 t | qhull Tv

Despite the improvements in Qhull 3.1, these distributions may lead
to wide facets, points outside of the computed hull, and O(n) longer
execution time.  They are similar to narrow distributions which are
known to be troublesome for Qhull.   For a discussion, see
     http://www.geom.umn.edu/software/qhull/html/qh-impre.htm#limit

Please let me know of any difficulties or missing/unclear documentation.

						--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.