fishkin@pixar.UUCP (Ken Fishkin) (04/07/88)
Does any kind soul have code for finding the convex hull of an
arbitrary set of 3-D points, preferably in O(NlogN) time?
thanks,
Ken Fishkin ...{ucbvax,sun}!pixar!fishkin
--
Ken Fishkin ..ucbvax!pixar!fishkinspencer@spline.eecs.umich.edu (Spencer W. Thomas) (04/07/88)
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)
rmf@actnyc.UUCP (Robert M. Fuhrer) (04/13/88)
In article <818@zippy.eecs.umich.edu> spencer@spline.eecs.umich.edu (Spencer W. Thomas) writes: > >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) In fact, there is an on-line (incremental) O(n*log n) algorithm for computing convex hulls. I refer you to the July 1979 issue of Communications of the ACM. In it, F. P. Preparata describes the use of a height-balanced tree which orders the points by their polar angles with respect to some internal point. The (n+1)th point is then located between two successive points (wrt angle), and categorized according to whether it lies within the hull from the previous iteration. If outside, two points in the previous hull (not necessarily consecutive) are found which, together with the new point, form part of the boundary of the new hull. The probes into the ith set of points (with i members) representing the ith hull, being all O(log i), yield an O(n*log n) algorithm when n iterations are applied to a set of n points. -- The Foundation for Unmitigated Sillyness uunet!actnyc!rmf Department of Redundancy Department City of Kansas City, Kansas