# On using a 3D convex hull to compute a 2D Voronoi diagram

I am working in a computing environment that has the facility to compute general nD convex hulls and not much else in the way of computational geometry. The routine, given a set of points, gives the vertices of the convex hull and edge connectivity information.

I want to use this method to compute the (bounded) Voronoi diagram of a set of 2D points. Some literature research (e.g. this paper) shows that you can "lift" the 2D points by adding a third coordinate, and then generate the convex hull of those points. The faces of the convex hull can then be projected to get the Delaunay triangulation, while computing the normals of those faces yields the Voronoi vertices.

My problem is that although I am able to use this approach to compute the inner Voronoi vertices in a bounded diagram, I am unable to use this to compute the frontier vertices (the intersection of the infinite rays in the diagram with the rectangular bounds). I may not have searched enough, but I was unable to find information on how to do so.

One possibility I thought of was to find the intersecting half-spaces on each vertex of the 2D convex hull (including the rectangle bounds), but I was wondering if there are more efficient/elegant approaches. Literature pointers will be immensely appreciated.