MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.

My problem is to find the vertices that make up each face of a convex polyhedron. At my disposal are a set of planes, with each plane corresponding to a face. Each plane is derived from exactly three points that I know already exist on the corresponding face.

How do I solve this problem in an efficient manner? Apologies if this isn't in the right section, since it involves both math and computer science.

share|cite|improve this question
You could use the software qhull to compute the intersection of halfspaces. See this link for qhull's halfspace intersection capabilities. – Joseph O'Rourke Aug 4 '13 at 2:01
Thanks for the link. I played around with qhull, and while it produces correct results, it does not do so quickly if you simply call the program multiple times, unless there's something I'm not doing right. – Kein Mitleid Aug 4 '13 at 4:18
up vote 4 down vote accepted

For the description of a pretty good algorithm see Avis and Fukuda. For an efficient implementation (in any dimension), and much additional discussion and references, see Komei Fukuda's page.

share|cite|improve this answer
After a bit of debating amongst myself, I decided to accept this answer. I'll do some reading on the links you sent me. – Kein Mitleid Aug 4 '13 at 4:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.