Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Is there a simple algorithm to compute the convex polyhedron (as a mesh with verticies, edges, and faces) resulting from the intersection of a set of infinite halfspaces? This is essentially a CSG (constructive solid geometry) to B-rep (boundary representation) problem. I am aware that CGAL has the Nef-polyhedra capabilities, but using CGAL is way overkill and complicated.

The actual problem I have is this: Given a 3D lattice specified by its 3 primitive lattice vectors, determine the Voronoi cell of a single lattice point.

The problem is that I actually need the polyhedral surface rather than just the volume, so I need a boundary representation.

share|cite|improve this question

Try qhalf from the qhull package.

share|cite|improve this answer
That's all well and good, but I'd like a description of how it does the computation. The manual mentions that by duality, it is reduced to a convex hull problem. I don't think I see how that is. – Victor Liu Oct 7 '11 at 0:40
Section 11.4 of Computational Geometry by de Berg et al. is about duality. David Mount's notes contain a summary. See lecture 07. – lhf Oct 7 '11 at 0:58

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.