Optimization Problems in Computational Geometry

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

The general theme in this project is the design, analysis, and implementation of optimization algorithms for geometric problems. The research will concentrate on the following topics: Geometric networks: How to construct a good network that connects a given set of sites. Given such a network, how to use geometric information to compute (exact or approximate) shortest paths between any two given sites. Given such a network, how to modify it so that all sites have good connections. Geometric data structures: How to organize geometric data, such that an informative "summary" of the subset of the data that is contained in a query region can be computed. Geometric problems in computer-aided design: How to apply techniques from computational geometry to speed-up algorithmic processes in computer-aided manufacturing.