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...[ Read more ]

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.