The Taub Faculty of Computer Science Events and Talks

Voronoi diagrams are one of the most powerful data structures in computational geometry. Barequet, Dickerson, and Goodrich [D&CG 2001] introduced the notion of polygon-offset distance function for points. The polygon-offset distance function is more natural than scaling and is useful to model many problems which arise in manufacturing tolerances. Using this distance function, they studied the nearest- and farthest-site Voronoi diagrams of point sites in the plane. In this talk, I will generalize the polygon-offset distance function to convex polygonal objects and present the combinatorial complexity of the nearest - and farthest-site Voronoi diagrams of line segments and convex polygons.