compute convex hull in n dimensions

Discuss interdimensional programming, Java applets and so forth.

compute convex hull in n dimensions

Postby bo198214 » Thu Jan 19, 2006 11:13 pm

quickfur wrote:However, one BIG obstacle I'm facing right now is that for some of the diagrams I want to do, I need to implement a convex hull algorithm.
...
I should probably move the core projection and polytope code into C++ and optimize it.


There are already convex hull algorithms out there (and even I programmed a 4d-convex hull-algorithm several years ago - but never knew if it would always compute the correct hull :wink: ). The question is only whether its easier to incorporate the foreign code or to develop it himself...

For foreign code look at:
polymake (though the gcc crashes when compiling ... on linux, on windows, with two versions of gcc :( )
References to convex hull programs.
Especially the cdd is written in c/c++ and a kind of reference implementation.

There are the dual problems of finding the hull (the halfspaces) from given points and finding the vertices from intersecting halfspaces.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Re: compute convex hull in n dimensions

Postby quickfur » Fri Jan 20, 2006 9:46 pm

bo198214 wrote:[...]For foreign code look at:
polymake (though the gcc crashes when compiling ... on linux, on windows, with two versions of gcc :( )
References to convex hull programs.
Especially the cdd is written in c/c++ and a kind of reference implementation.

There are the dual problems of finding the hull (the halfspaces) from given points and finding the vertices from intersecting halfspaces.

Thanks, I'll take a look at those.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby quickfur » Thu Feb 02, 2006 7:24 pm

I'm just wondering, how well do these different convex hull implementations handle degenerate polytopes? The kind of polytopes I'm interested in are highly degenerate (e.g. the regular polytopes and the uniform polytopes, some of which have great rhombicuboctahedral cells in which a large number of vertices lie in the same 3-plane).

Also, what I really want in the end is a complete face-lattice enumeration. In order to create adequate projections, having the complete face lattice is essential.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Thu Feb 02, 2006 10:03 pm

I would assume they handle degenerations very well (because they are made by mathematicians *g*). But admit that I never worked with these algorithms.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Thu Feb 02, 2006 10:51 pm

bo198214 wrote:I would assume they handle degenerations very well (because they are made by mathematicians *g*). But admit that I never worked with these algorithms.

On the contrary, many convex hull implementations come with a caveat that they may not work as well if there are a lot of degeneracies. Komei Fukuda's implementation of the Double Description method is explicitly designed to handle degeneracies well, but other convex hull algorithms appear to assume that a simplicial decomposition is what is wanted. Some implementations explicitly state that poor performance or incorrect output may result given degenerate input.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Programming

Who is online

Users browsing this forum: No registered users and 4 guests