From: pdx4d@teleport.com (Kirby Urner)
Newsgroups: sci.math
Subject: Polyhedron-from-points algorithm sought
Date: Thu, 16 Feb 1995 13:47:52 LOCAL

Request for Algorithm Ideas:

I have a dispersion of points about the origin.  In this case they're
all equidistant from (0,0,0) and lots of symmetries.  What I'm looking
for is a computer algorithm, or the rough idea of one, that will draw
chords between these points giving a polyhedron.

The best I've come up with so far is something like:  omnitriangulate
the surface.  Start with triangle A and check an adjacent triangle B.
If B slants the same way in space, then it is part of the same facet,
so merge it with A by removing the separating chord.  Continue, merging
all similarly oriented, adjacent facets into single facets.

That sounds a lot easier than it is.  All I have to start are the
(x,y,z) coordinates of my dispersion.  Omnitriangulating, figuring
out what's adjacent, and computing "slant in space" are all problematic
for me.  I'm willing to forge ahead, but if there's a much more elegant
algorithm that'd save me from barking up the wrong tree, I'd love to
hear about it.

Email replies preferred:  pdx4d@teleport.com

Kirby Urner
Portland, Oregon
USA

------------------------------------------------
Kirby Urner & Dawn Wicca           "All realities are virtual" -- KU
Portland (PDX), Oregon
pdx4d@teleport.com
Web: <a href="http://www.teleport.com/~pdx4d/>Kirby Urner</a> 

==============================================================================

From: pdx4d@teleport.com (Kirby Urner)
Newsgroups: sci.math
Subject: Convex hull algorithms...
Date: Sat, 18 Feb 1995 00:31:45 LOCAL
[post empty except for the following quote, and KU sig - djr]

From: Maurice.Rojas@univ-rennes1.fr
Date: Fri, 17 Feb 1995 21:17:49 +0100
To: pdx4d@teleport.com
Subject: Convex hull algorithms...

Dear Kirby,
	Hello, I saw your post on sci.math and thought I could give you 
a little off-the-cuff advice.
	There are quite a few algorithms for the problem you want to 
solve and there is an excellent description of them in two books: 
One of them is authored by H. Edelsbrunner, the author is authored 
by Preparata and Shamos.  Both of them are entitled ``Computational 
Geometry...'' or at least contain those words in their title.  I 
don't know what your mathematical background is, but those two 
books cover most of what is already known about your problem.
	In any case, I can give you the following quick summary. 
(I apologize in advance if there are any errors.)  I don't know 
what you mean by omnitriangulating, but I assume you mean forming  
a lot of triangles and then testing to see which of these can 
form facets.  There are n(n-1)(n-2)/6 such triangles and 
checking to see if any one of them forms part of a facet amounts 
to verifying that all the remaining points lie completely on 
one side of the plane formed by that triangle.  That means 
checking n-1 points.  So, roughly speaking, your algorithm 
requires O(n^4) such checks.  Each such check can be reduced 
to computing the sign of a 3 x 3 determinant, so up to a 
constant, your algorithm has complexity O(n^4).
	However, there is an O(n^2) algorithm.  This turns out 
to be the best asymptotic complexity possible, and you can 
prove this through some more advanced techniques.  In any case, 
one of the O(n^2) algorithms (I think there are several) 
is called ``gift-wrapping.''  Basically, one first begins 
by sorting the points lexicographically, which takes time 
O(n log n).  One then finds just 3 points which lie on a face. 
After that, one tries to fold the plane defined by that triangle 
until it begins to ``wrap around'' the remaining points.  The 
folding procedure involves doing checks similar to the one 
I mentioned above, but by having sorted the points a priori 
(and doing some other pre-processing which I forget), one 
cuts down tremendously the amount of work needed.  So, 
you get O(n log n) + O(n^2) = O(n^2) arithmetic steps.
	More generally, there are algorithms for computing 
the convex hull of n points in d dimensions (such an 
object is called a polytope or polyhedron, depending on 
your religion) which have asymptotic complexity 
O(n^(1+[d/2])), where [x] denotes the greatest integer 
smaller than x.  For d>=3, these algorithms are asymptotically 
optimal.  For d=2, you can go a little faster: O(n log n). 
Thus you can find the smallest polygon bounding a set of 
points in the plane within that number of arithmetic steps, 
and it turns out that you can't go any faster.  However, 
if you refine your complexity estimates (stated them not 
only in terms of n, also in terms of other information), 
you can go even faster.  There is an algorithm in the 
plane which can compute a convex hull in O(n log h) 
arithmetic steps, where your new parameter h is the 
number of points on the boundary of the polygon.
	So, for concluding remarks, I should say that 
I've assumed all along that n is the number of points 
in your set.  (Sorry I didn't say that earlier!)  
I should also say that the complexity results are actually 
quite interesting and have a funny history.  Seidel 
(I think in the late 70's) derived the optimal convex 
hull algorithms, but only proved that they were optimal 
in (I think) odd dimension.  It wasn't proved until 
the late 80's (or early 90's) that these algorithms 
were also optimal in even dimension (Bernard Chazelle 
did this).  
	Other comments, your problem is referred to in 
the computational geometry community as the ``convex 
hull problem in 3 dimensions.''  It is also intimately 
related to the problem of computing Voronoi diagrams 
(diagrams which subdivide space in a special way) and 
also related to the problem of volume computation. 
These connections are worth knowing.  As a final note, 
there are certain nonsingularity conditions implicit 
in some of the algorithms (e.g., when in 3 dimensions, 
no 4 points can lie on the same sphere or no 4 points 
can lie on the same plane, or something like that), 
but these assumptions can be dealt with.  One of the 
books I mentioned above states an algorithm which 
explicitly deals with this.  There are other ways 
to deal with these sorts of degeneracies (for instance, the 
recent paper of Canny and Emiris, ``An Efficient 
Approach to Removing Geometric Degeneracies,'' Proc. 8th 
ACM Symp. on Computational Geometry, pp. 74-82, 1992), 
but I won't go into them.
	Hope this helps.  If you would like to post this, 
feel free to.

					Best Wishes,

					Maurice
==============================================================================

Date: Fri, 17 Feb 95 12:01:36 CST
From: rusin (Dave Rusin)
To: pdx4d@teleport.com, rusin@math.niu.edu
Subject: Re: Polyhedron-from-points algorithm sought

>Intriguing.  This would give an omnitriangulated polyhedron,
>no?  Then I'd need to eliminate triangles that are internal
>to the same facet.

I thought "omnitriangulated" meant you were going to start with
all  (n choose  3) trangles joining all triples of points and
then discard the ones which were not exterior.

I'm not sure of the meaning of your last sentence. If you mean you'll
have to eliminate triangles which lie in the interior of a newly-constructed
polyhedron, you're right; I assumed you were going to keep a list of
sets of 3 vertices, each set representing a triangle; then you would
simply remove one such set from your list every time you considered a
new point (and thus added 3 triangles in place of the removed one).

If instead your last sentence is meant to imply that you have to remove
line segments separating two triangles which share a common edge and
lie on one plane, you're right, if you want these edges not to show. 
You could keep this data as you went along: for each triangle you store
not just the 3 vertices but also pointers to the three triangles adjacent
to it across the edges (the extra data is easily updated when you replace
one triangle by 3 new ones). Then, when done, you can test each pair of
adjacent triangles for coplanarity (a simple determinant condition)
before drawing the line segment, with a control statement to draw only
if the triangles are noncoplanar. So for example the dodecahedron would
look like 12 pentagons, but we would have stored it internally as a set
of 36 triangles, with some common edges erased. This bookeeping at most
increases computation time by a common factor.

I still think there's an  O(N logN) algorithm but I can't get past the
critical combining step. Oh well.

dave

==============================================================================

Date: Fri, 17 Feb 1995 10:20:31 -0800
To: rusin@math.niu.edu (Dave Rusin), rusin@math.niu.edu
From: pdx4d@teleport.com (Kirby Urner)
Subject: Re: Polyhedron-from-points algorithm sought

At 12:01 PM 2/17/95 CST, Dave Rusin wrote:
>>Intriguing.  This would give an omnitriangulated polyhedron,
>>no?  Then I'd need to eliminate triangles that are internal
>>to the same facet.
>
>I thought "omnitriangulated" meant you were going to start with
>all  (n choose  3) trangles joining all triples of points and
>then discard the ones which were not exterior.
>
>I'm not sure of the meaning of your last sentence.

>If instead your last sentence is meant to imply that you have to remove
>line segments separating two triangles which share a common edge and
>lie on one plane, you're right, if you want these edges not to show. 

That's what I meant.  I guess the simple determinant condition is
what's got me stumped.  I'll hit the books when I get the time.
It looks like a big job, but doable.

Thanks for your help.

Kirby
------------------------------------------------
Kirby Urner & Dawn Wicca           "All realities are virtual" -- KU
Portland (PDX), Oregon
pdx4d@teleport.com
Web: <a href="http://www.teleport.com/~pdx4d/>Kirby Urner</a> 

==============================================================================

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Polyhedron-from-points algorithm sought
Date: 17 Feb 1995 15:35:13 GMT

In article <pdx4d.152.03DB3ABC@teleport.com>,
Kirby Urner <pdx4d@teleport.com> wrote:
>I have a dispersion of points about the origin.  In this case they're
>all equidistant from (0,0,0) and lots of symmetries.  What I'm looking
>for is a computer algorithm, or the rough idea of one, that will draw
>chords between these points giving a polyhedron.

Let's assume you can first find 4 points whose convex hull includes the
origin. Proceed by induction to create the convex hull of  n  points,
as a union of (2n-4) triangles. Indeed, if one polyhedron is given and a 
point  P  is not already on it, then (since all the points lie on the
unit sphere)  P  is outside the existing polyhedron. Determine which of
the existing faces intersects the line segment from  P  to the origin;
if it has vertices  P1 P2 P3, then replace that triangle with the 3
trangles  P1 P2 P, P P2 P3, and P1 P P3. (A slight variation is needed 
if the line segment intersects two triangles). Continue until all points
are included.

If you have  N  points at first, this will create output of length  O(N)
with computation time  O(N^2). If that's not good enough, I suppose an
O(N logN) algorithm exists, since this looks like a sorting problem. The
crucial step in such an algorithm eludes me: given two polyhedra already
triangulated, each spanned by points on the unit sphere, combine the
spanning sets and get a new polyhedra in a way which only requires comparison
of vertices in one set with triangles in the other.

dave