HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Mechanical Engineering >
MECH Doctoral Theses >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/7133
Title: Geodesic iso-contours, bisectors and voronoi diagrams on triangulated meshes and their applications
Authors: Chen, Zhanqing
Issue Date: 2011
Abstract: Voronoi diagram is an elegant spatial structure which has found diverse applications in a variety of disciplines in natural science and engineering, including pattern recognition, motion planning, operational research, information retrieval, biological morphology, etc. Computing Voronoi diagrams on triangulated surfaces is challenging because the construction needs computing the geodesic distance metric which is more complex than the Euclidean distance metric, and needs studying the special structure inherent in the Voronoi diagrams on triangulated meshes, such as break points and hypobolic segments, which do not exist in the Euclidean space. A desirable algorithm should be designed specifically based on the intrinsic structure and an efficient method of computing geodesic distances on triangulated surfaces. In this thesis, we first extend the well-known MMP method for computing exact geodesic distance from one source point to multiple source points, which enables the construction of Voronoi diagrams based on a more precise distance metric as compared to using only the approximation geodesic distance metric. We then study the analytic structure of Voronoi diagrams, bisectors, and iso-contours on triangulated surfaces, hierarchically, since iso-contours are a superset of bisectors and Voronoi diagrams consist of bisectors mutually exclusive or semi-exclusive. It is demonstrated in the thesis that their intrinsic structure can be captured and implemented through using our proposed algorithms. The contribution of our work is a suite of efficient algorithms based on the unique structure analysis obtained by us that are able to compute complete iso-contours, bisectors and Voronoi diagrams. Our work overcomes the shortcomings of earlier simple interpolation methods based on the approximate geodesic metric, which are not accurate and incomplete in nature. In addition, several applications related to the properties of Voronoi diagrams on triangulated surfaces are explored by employing our proposed algorithms.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2011
xiv, 125 p. : ill. ; 30 cm
HKUST Call Number: Thesis MECH 2011 ChenZ
URI: http://hdl.handle.net/1783.1/7133
Appears in Collections:MECH Doctoral Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

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