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 twofold. 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 
View fulltext via DOI
Files in this item:
File 
Description 
Size 
Format 
th_redirect.html


345 B 
HTML 
Copyrighted to the author. Reproduction is prohibited without the authorâ€™s prior written consent. 
