Approximation Algorithms in Computational Geometry

点击翻译按钮获取中文摘要

This project investigates the topic of approximation algorithms in computational geometry, with focus on the two problems: polyhedral surface modeling and Euclidean shortest paths. In surface modeling, one tries to construct a polyhedral model of a complex surface, based on a set of unordered sample points. The complexity of constructing and manipulating the model depends on its number of vertices and faces, and therefore a natural optimization goal is to minimize these features in the model without exceeding a pre-specified error tolerance. The project studies various surface-modeling problems within the formal framework of computational geometry, and analyzes the issues of computational complexity. The problem of computing shortest paths is central to robotics and autonomous navigation. The research investigates approximation algorithms for shortest path problems in two and three dimensions. In two dimensions, the query version of the shortest path problem is studied: preprocess a set of polygonal obstacles so that given two points p and q, the distance between them can be determined in polylogarithmic time. In three dimensions, the goal is to design simpler and more practical alternatives to the exact algorithms for shortest paths among polyhedral solids or on a polyhedral surface.