CGGC Seminar: Voronoi diagram of line segments and convex polygons with convex polygon-offset distance functions

Minati De (CS, Technion)
Sunday, 11.1.2015, 14:30
Taub 401

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.

Back to the index of events