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.