bergman@alanine.cs.unc.edu (Larry Bergman) (09/14/90)
I'm looking for references/implementations of 3D convex hull algorithms. I'm familiar with 2D algorithms, but not 3D. I'll appreciate any pointers. Larry Bergman
mucke@m.cs.uiuc.edu (Ernst P Mucke) (09/14/90)
There is a whole chapter on CH algorithms in
Herbert Edelsbrunner
Algorithms in Combinatorial Geometry
(EATC monographs on theoretical computer science; v 10)
Springer Verlag, Berlin, 1987
ISBM 0-387-13722-X (US)
where he discusses the Beneath-Beyond Method for d dimesions;
complexity: O (n log(n) + n^D) time and and O (n^D) space, where n
is the number of points and D = floor ((d + 1)/2). An O (n log(n))
Devide-and-Conquer algorithm which works for 3d only is also in there.
Another reference would be, eg,
Raimund Seidel
Constructing higher-dimensional convex hulls at log cost per face.
In Proc 18th Ann ACM Symp, 1986, p404--413.
Here at UIUC, we (Edelsbrunner's group) have also an implementation
of the Beneath-Beyond method. Send me email, if interested.
--
Ernst Mucke, Dept of Computer Science, U of Illinois at Urbana-Champaign
mucke@uiuc.edu {convex,uunet}!uiucdcs!mucke mucke%uiuc.edu@uiucvmd.bitnet
--
--
Ernst Mucke, Dept of Computer Science, U of Illinois at Urbana-Champaign
mucke@uiuc.edu {convex,uunet}!uiucdcs!mucke mucke%uiuc.edu@uiucvmd.bitnetroger@everexn.com (Roger House) (09/18/90)
In <16029@thorin.cs.unc.edu> bergman@alanine.cs.unc.edu (Larry Bergman) writes: >I'm looking for references/implementations >of 3D convex hull algorithms. I'm familiar >with 2D algorithms, but not 3D. I'll >appreciate any pointers. Introduction to Computational Geometry, Preparata and Shamos, Springer-Verlag, NY, 1985 describes a 3d hull algorithm. A real-world implementation of the algorithm in Preparata and Shamos is described by Day, A.M., "The Implementa- tion of an Algorithm to Find the Convex Hull of a Set of Three-Dimensional Points", ACM Transactions on Graphics, vol. 9, no. 1 (Jan. 1990), 105-132. The latter paper is very interesting in that it shows that "[A]s is often the case with geometric algorithms, the original publication tends to give a rather concise strategic outline that emphasizes the complexity analysis but glosses over implementation issues." Roger House
buchanan@cs.ubc.ca (John Buchanan) (09/18/90)
In article <1990Sep17.193645.4486@everexn.com> roger@everexn.com (Roger House) writes: >In <16029@thorin.cs.unc.edu> bergman@alanine.cs.unc.edu (Larry Bergman) writes: > >>I'm looking for references/implementations >>of 3D convex hull algorithms. I'm familiar >>with 2D algorithms, but not 3D. I'll >>appreciate any pointers. > >Introduction to Computational Geometry, Preparata and Shamos, Springer-Verlag, >NY, 1985 describes a 3d hull algorithm. A real-world implementation of the >algorithm in Preparata and Shamos is described by Day, A.M., "The Implementa- >tion of an Algorithm to Find the Convex Hull of a Set of Three-Dimensional >Points", ACM Transactions on Graphics, vol. 9, no. 1 (Jan. 1990), 105-132. > >The latter paper is very interesting in that it shows that "[A]s is often the >case with geometric algorithms, the original publication tends to give a >rather concise strategic outline that emphasizes the complexity analysis but >glosses over implementation issues." The flavor of this article is best described by a sentence from the introductory paragraph, and I quote. 'For example, experiment has revealed that this algorithm would appear to have worst case complexity O(n^2) and not O(nlogn) as was previously thought.' This strikes me as a somewhat hesitant result. ========================================================================= | |===============================| | John Buchanan (juancho) | buchanan@cs.ubc.ca | | |===============================| | Imager | (604) 228-2218 | | Department of Computer Science |===============================| | University of British Columbia | Standard disclaimer | | Vancouver, BC, Canada | included in this | | | box, right here. | =========================================================================