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.