Path: utzoo!attcan!uunet!know!zaphod.mps.ohio-state.edu!rpi!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!mucke
From: mucke@m.cs.uiuc.edu (Ernst P Mucke)
Newsgroups: comp.graphics
Subject: Re: 3D convex hull algorithms
Message-ID: <1990Sep13.225935.14021@ux1.cso.uiuc.edu>
Date: 13 Sep 90 22:59:35 GMT
References: <16029@thorin.cs.unc.edu>
Sender: news@ux1.cso.uiuc.edu (News)
Reply-To: mucke@m.cs.uiuc.edu.UUCP (Ernst P Mucke)
Organization: University of Illinois, Dept. of Comp. Science, Urbana
Lines: 29

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