Given a finite set S = {p1, p2, …, pn} of point sites in the plane, the classical Voronoi diagram subdivides the plane into regions, one for each point in S.  Given a point x in the plane, that point is in the region for the site pi if pi is the closest point in S to x.   The notion of Voronoi diagram may be generalized by varying the underlying geometric space, by allowing sites to be arbitrary sets, or by weighting the sites. 

Brown, Aurenhammer, Edelsbrunner and many others have used projective geometry to encode various types of generalized Voronoi diagrams as ``lifting'' problems wherein the diagram in R^d is computed by translating defining conditions in R^d to one dimension higher,  so that the diagram in R^d can be obtained by finding a polyhedron in R^{d+1} and then projecting the faces to R^d to get the cells of the diagram. 

We use Lie sphere geometry to describe two large classes of generalized Voronoi diagrams that can be encoded as  lifting problems.  (We first present a brief overview of Lie sphere geometry.)  The first class of diagrams includes those defined in terms of extremal spheres in the space of empty spheres, and the second class includes minimization diagrams for functions that can be transformed into restrictions of affine functions to quadric hypersurfaces. These results unify and generalize previously known descriptions of generalized Voronoi diagrams as lifting problems. 

This is joint work with John Edwards (Department of Computer Science, Utah State University) and Egan Schafer (Idaho State University).