Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/554

Algorithms for computing some geometric diagrams

Authors Vigneron, Pierre Antoine Emile
Issue Date 2002
Summary 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.
Note Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2002
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 345 B HTML