Tracy Payne, Idaho State University

Title: Generalized Voronoi Diagrams and Lie Sphere Geometry

Abstract: 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. It has long been known that efficient convex hull algorithms to compute generalized Voronoi diagrams can be based on Moebius geometry. We use Lie sphere geometry to unify previous results and to obtain new results relating generalized Voronoi diagrams, convex sets and the Lie quadric. This is joint work with John Edwards.