I am pleased to announce a new version of Qhull for general dimension convex hull, Delaunay triangulation, and Voronoi diagrams. This is the first program to (empirically) handle roundoff error in 3-d and above. For example, it approximates the exact convex hull of thousands of points near the surface of a cube. Existing programs may produce concave edges, facets with flipped orientation, and edges with more than two incident facets. Qhull is based on the Quickhull algorithm. It extends the 2-d algorithm with the n-d Beneath-beyond algorithm. It is similar to Clarkson and Shor's randomized incremental algorithm using conflict lists. The difference is that Quickhull selects the furthest point on a conflict list instead of a random point. Empirically, this makes Qhull output-sensitive. Qhull appears to be the fastest available algorithm in 3-d and higher. Version 2 has options to merge non-convex facets. The result is an approximate convex hull that sandwiches all possible exact convex hulls. Empirically, this handles arbitrary amounts of round-off error and imprecision in 2-d, 3-d, and 4-d. In 5-d and higher, it may fail to produce a good approximation. The program also includes options for graphical output, partially constructed hulls, input transformations, randomization, tracing, and execution statistics. The program can be called from within your application. Source code in C for general dimension convex hull and Delaunay triangulation (qhull) is now available by anonymous ftp: mkdir qhull cd qhull ftp geom.umn.edu user: anonymous password: [your user id] cd pub get qhull.tar.Z (Version 1 is qhull-1.0.tar.Z) quit uncompress qhull.tar.Z tar xf qhull.tar make You can view the results in 2-d, 3-d and 4-d with geomview (Iris version by ftp geom.umn.edu:/pub/software/geomview/geomview-sgi.tar.Z, Next version by ftp of /pub/software/geomview/geomview-next.tar, Sun version by ftp of /pub/software/geomview/geomview-sun.x11-beta.tar.Z). Version 1.0 is available for the Macintosh in pub/software/qhull.sit.hqx It reads point coordinates from a standard file, and returns output to a standard file. There is no graphical output. Convex hull is an easy way to build convex polytopes (just list the vertices). The algorithm also produces approximate convex hulls. For example, we have produced the approximate convex hull of 12,000 points in R^6, randomly distributed in the unit cube. The distribution includes .ps files for Barber, C.B., Dobkin, D.P., and Huhdanpaa, H., "The Quickhull algorithm for convex hull," Technical Report GCG53, The Geometry Center, Univ. of Minnesota, July 1993. Abstract: The convex hull of a set of points is the smallest convex set that contains the points. This paper presents a convex hull algorithm that combines the 2-d Quickhull algorithm with the general dimension Beneath-beyond algorithm. It is similar to the randomized, incremental algorithms for convex hull and Delaunay triangulation. Our algorithm is simpler, uses less memory, and allows good use of virtual memory. A simple modification produces an approximate cOnvex hull. We provide empirical evidence that the algorithm runs faster and is output sensitive. --Brad Barber (barber@das.harvard.edu)