From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson)
Newsgroups: comp.graphics.algorithms
Subject: Re: Searching for Preparata and Hong's algorithm
Date: 28 Mar 96 03:54:54 GMT

frank berwanger <franky@cscip.uni-sb.de> writes:

>I'm looking for Preparata and Hong's three-dimensional
>convex hull algorithm. Does anybody know where I can
>find an implemented version of this?

I recommend reading the following paper, which describes an
implementation of P&H's algorithm.  However, I do *NOT* recommend
using the approach the paper describes.  Day's implementation has a
number of problems, including omission of several degenerate cases,
complete lack of memory management, using trigonometry instead of
linear algebra to determine orientations of tetrahedra, and the
(perhaps forgivable in 1990) assumption that points are in general
position.  However, the paper will give you some idea of just how
complex the algorithm is.

@article{d-iafch-90
, author =      "A. M. Day"
, title =       "The implementation of an algorithm to find the convex
		hull of a set of $3$-d points"
, journal =     "ACM Trans. Graph."
, volume =      9
, number =      1
, year =        1990
, pages =       "105--132"
, keywords =    "implementing algorithms, three-dimensional, convex
		hull, points"
}

I'm not aware of any complete implementations of Preparata and Hong's
algorithm, and that's probably just as well.

I don't mean to cast aspersions on the people who discovered the
algorithm -- it was a great theoretical acheivement -- but there are
much simpler and more practical 3d convex hull algorithms available.
Preparata and Hong's algorithm is full of ugly special cases that more
recent algorithms don't have to worry about.  The description of the
algorithm in Edelsbrunner's textbook requires 15 pages!  (As far as I
know, this is the only complete description anywhere in the
literature.)

@book{e-acg-87
, author =      "H. Edelsbrunner"
, title =       "Algorithms in Combinatorial Geometry"
, series =      "EATCS Monographs on Theoretical Computer Science"
, volume =      10
, publisher =   "Springer-Verlag"
, address =     "Heidelberg, West Germany"
, year =        1987
, keywords =    "design of algorithms, discrete geometry, book"
}

You're much better off implementing an incremental algorithm, perhaps
with some initial preprocessing to get rid of "obviously" non-extreme
points.  The code will be easier to write, easier to optimize, much
smaller, and probably much faster (especially if the points are
inserted in random order).

-- 
Jeff Erickson
jeffe@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe