# Algorithm to compute mesh from intersection of infinite halfspaces

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.

-

Try qhalf from the qhull package.

-
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