M.Sc Thesis

M.Sc StudentKloper Dimitry
SubjectGeometries and Topologies of Triangulations of Point Sets
DepartmentDepartment of Computer Science
Supervisors PROF. Gill Barequet
PROF. Chaim Craig Gotsman


In this thesis we define a set of techniques and methodologies for optimization of planar meshes. A mesh may consist of several vertices, each having distinct coordinates, connected by a set of edges forming a valid triangulation of the point set.

In the first stage, we define and develop a set of generic optimization algorithms. Each algorithm affects different aspects of the mesh, its connectivity and its geometry. The focus is on generic properties of the optimization, with an attempt to avoid using information about specific properties of the point set or its connectivity. For the connectivity optimization we develop a generic algorithm which performs the optimization by edge flipping, making dynamic optimization decisions based on the supplied cost function. For the geometry optimization we develop a generic algorithm that affects the geometric point locations based on the supplied cost function. The generic properties of these algorithms are experimentally studied, including dependency on the cost function, ability to escape the local minima, dependency on the initial mesh conditions and other factors.

In the second stage, we define and develop a connectivity realization algorithm. Connectivity realization denotes a process of searching for the connectivity (a valid triangulation) for a point set, which produces the required geometry under the geometry optimization. We consider connectivity realization as a search algorithm in the space of the valid triangulation for the particular geometry. We provide a standard search mechanism based on the A* algorithm and develop an efficient heuristics based on the generic properties of the geometry optimization.