Path: utzoo!attcan!uunet!nuchat!sugar!emcalc
From: emcalc@sugar.hackercorp.com (William M. Schmidt)
Newsgroups: comp.graphics
Subject: Re: Convex hulls
Summary: Jarvis's march generalizes to 3-d
Keywords: How do you calculate the convex hull in 3d?
Message-ID: <4683@sugar.hackercorp.com>
Date: 6 Dec 89 05:52:54 GMT
References: <1989Dec5.220421.10486@eplrx7.uucp>
Organization: Sugar Land Unix - Houston
Lines: 11


The Jarvis march method in 2-d can be generalized to 3-d. It's called
"gift wrapping" because that's what it resembles. A good reference for
these sort of geometrical problems is "Computational Geometry - An
Introduction" by Preparata and Shamos, 1985, Springer-Verlag. I believe
that this is an O(N^2) algorithm in 3-d.

-- 
Bill Schmidt                 |
Texas Accelerator Center     | "Eagles may soar, but a worm never
emcalc@sugar.hackercorp.com  |  gets sucked into a jet engine"