A COMPACT PIECEWISE-LINEAR VORONOI DIAGRAM FOR CONVEX SITES IN THE PLANE

In the plane the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one- dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using O(k) line segments, that is sufficient for logarithmic time post -office location queries and motion planning. If these sets are polygo ns with n total vertices given in standard representations, we compute this diagram optimally in Theta(k log n) deterministic time for the E uclidean metric and in O (k log n log m) deterministic time for the co nvex distance function defined by a convex m-gon.