Optimization Problems in Computational Geometry

这个项目的总主题是几何问题的优化算法的设计和分析。研究将集中在以下主题：* 几何生成器网络：如何构建一个稀疏网络，连接一组给定的站点，使得对于任何两个站点，它们在网络中的最短路径距离近似等于它们的直线距离。给定这样一个网络，如何使用几何信息来计算（精确或近似）任意两个给定站点之间的最短路径，如何仅使用局部信息增量地计算这样一条路径。几何图形增强：如何向现有的几何网络添加少量链接，以使生成的增强网络中的最长距离最小化。对于给定的几何网络及其上的给定位置，如何计算网络中距离最远的位置。*几何图的最优子图：给定一组红点和蓝点，如何计算最短（或最长）生成树，其中每个链接连接一个红点和一个蓝点。如何计算这样的树，如果没有两个链接被允许交叉。几何数据结构：如何组织几何数据，以便可以计算查询区域中包含的数据子集的信息性“摘要”。如何组织几何数据，其中每个数据元素属于某个类别，以便可以计算查询区域内的不同类别。

The general theme in this project is the design and analysis of optimization algorithms for geometric problems. The research will concentrate on the following topics:***Geometric Spanner Networks: How to construct a sparse network that connects a given set of sites such that for any two sites, their shortest-path distance in the network is approximately equal to their straight-line distance. Given such a network, how to use geometric information to compute (exact or approximate) shortest paths between any two given sites, how to compute such a path incrementally using only local information.***Geometric Graph Augmentation: How to add a small number of links to an existing geometric network, such that the longest distance in the resulting augmented network is minimized. For a given geometric network and given location on it, how to compute the locations in the network that are farthest away.***Optimal Subgraphs of Geometric Graphs: Given a set of red and blue points, how to compute a shortest (or longest) spanning tree in which each link connects a red point with a blue point. How to compute such a tree if no two links are allowed to cross.***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. How to organize geometric data in which each data element belongs to some category, such that the different categories inside a query region can be computed.