Tremendous progress has been made in the field of computational geometry in the last few decades. Efficient algorithms have been developed to solve geometric problems. However, there are many problems in computational geometry that do not yet have good algorithms or even do not have any algorithmic solutions. The main goal of this project is the development of new fundamental techniques in algorithms for solving those geometric problems.
This project aims to investigate a particular group of problems in computational geometry: problems in polygonal domains (or polygons with holes) in the plane. These problems are particularly interesting and fundamental because they model many geometric problems in the plane. The specific problems include computing shortest paths measured by Euclidean or other metrics, minimum link paths, other geometric paths, geodesic Voronoi diagrams, visibility polygons, geodesic diameter and center, polygon decomposition, facility locations, and geometric data structures, etc. The goal is to develop new algorithmic techniques for solving these problems efficiently. This research will bring diverse methodologies from other areas such as discrete mathematics, graph theory, operations research, combinatorial optimization, computational complexity, data structures, etc. The project is expected to greatly improve our understanding of the geometric structures of the problems in polygonal domains and to produce new algorithmic tools for solving these problems.
This research will potentially enrich the area of computational geometry by introducing new techniques. The algorithms and observations obtained from the project will also benefit computer science and other related disciplines where geometric algorithms are widely used. Another important part of this project is to train graduate students to practice in doing research, especially in developing algorithms for solving problems in computational geometry.
