Algorithms for computing some geometric diagrams

Abstract

We define a geometric diagram as a graph embedded in the plane, or in a surface, whose faces contain points sharing a geometric property. Our goal is to find efficient algorithms to compute some geometric diagrams. The motivation is two-fold. First the diagram itself may be interesting and will be the output of the algorithm. Second, it can be used for query problems, since localizing a query point in the diagram gives a geometric property of this point.

We study three types of diagrams: the restriction of the furthest site Voronoi diagram to the surface of a convex polytope, the straight skeleton of a polygon and the reachable region for a point moving within a convex polygon under the constraint that its trajectory has bounded curvature. In each case, we find new geometric properties of the diagram and then use them to develop an efficient algorithm to compute it.

Date of Award	2002
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology