Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!mailrus!umix!umich!spline.eecs.umich.edu!spencer
From: spencer@spline.eecs.umich.edu (Spencer W. Thomas)
Newsgroups: comp.graphics
Subject: Re: convex hull routines needed
Message-ID: <818@zippy.eecs.umich.edu>
Date: 7 Apr 88 15:55:32 GMT
References: <1704@pixar.UUCP>
Sender: news@zippy.eecs.umich.edu
Reply-To: spencer@spline.eecs.umich.edu (Spencer W. Thomas)
Organization: University of Michigan EECS, Ann Arbor
Lines: 13
UUCP-Path: spline!spencer


In article <1704@pixar.UUCP> fishkin@pixar.UUCP (Ken Fishkin) writes:
>
>    Does any kind soul have code for finding the convex hull of an
>arbitrary set of 3-D points, preferably in O(NlogN) time?
>

Preparata & Shamos ("Computational Geometry", Springer-Verlag, 1985),
give an NlogN algorithm for 3-D convex hull, if you have all the
points ahead of time.  If you are given one point at a time, and wish
to compute the convex hull incrementally ("on-line" is their term),
the best you can do is N^2.


=Spencer (spencer@crim.eecs.umich.edu)