HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >

Please use this identifier to cite or link to this item:
Title: Algorithms for computing some geometric diagrams
Authors: Vigneron, Pierre Antoine Emile
Issue Date: 2002
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.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2002
xi, 105 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 2002 Vigner
Appears in Collections:CSE Doctoral Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.