Optimization Problems in Computational Geometry

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

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.