Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!rochester!cornell!uw-beaver!ubc-cs!buchanan
From: buchanan@cs.ubc.ca (John Buchanan)
Newsgroups: comp.graphics
Subject: Re: 3D convex hull algorithms
Message-ID: <9622@ubc-cs.UUCP>
Date: 18 Sep 90 16:09:59 GMT
References: <16029@thorin.cs.unc.edu> <1990Sep17.193645.4486@everexn.com>
Sender: news@cs.ubc.ca
Organization: UBC Department of Computer Science, Vancouver, B.C., Canada
Lines: 39

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.	|
=========================================================================