BSF:201229:Efficient Algorithms for Geometric Optimization

该项目是美国-以色列计算机科学合作（USICCS）计划的一部分。通过这个项目，NSF和美国-以色列两国科学基金会（BSF）共同支持美国科学家和以色列科学家之间的合作。杜克大学和特拉维夫大学之间的这个合作研究项目旨在研究几何优化中的几个主题以及在各种应用领域中几何数据处理中出现的相关问题，例如传感器网络，成像，监视，导航，地理信息系统，建模和动画，网格划分，计算机图形学和视觉，生物信息学，机器人和制造。在这些应用程序中处理几何数据是具有挑战性的，因为这些数据通常是巨大的，具有不确定性，以分布式方式（例如，在传感器网络中）或以在线方式（例如，在流应用程序中）获得，并且可能涉及移动点（例如，在成像，动画和建模中）。所有这些特点使得数据处理成为一项相当艰巨的任务，需要设计新的算法技术来有效地处理数据。对于许多这样的问题，精确的算法，甚至是输入大小的多项式，都是不切实际的，需要近似算法。即使这样，使这些算法有效地依赖于误差参数往往是一项困难和具有挑战性的任务。该项目通过开发通用算法技术来解决上述挑战，例如计算几何摘要（包括核心集和随机样本），处理各种不确定性概率模型下的噪声几何数据，处理在线数据和处理动态数据（涉及运动物体）。目标的一些具体问题包括形状匹配、聚类和几何搜索。这些主题中的每一个都提出了有趣的算法问题，无论是理论还是实践，该项目将尽可能多地解决这些问题。

This project is funded as part of the United States-Israel Collaboration in Computer Science (USICCS) program. Through this program, NSF and the United States - Israel Binational Science Foundation (BSF) jointly support collaborations among US-based researchers and Israel-based researchers.This collaborative reserach project between Duke University and Tel Aviv University aims to study several topics in geometric optimization and related problems that arise in the processing of geometric data in a variety of application areas, such as sensor networks, imaging, surveillance, navigation, geographic information systems, modeling and animation, meshing, computer graphics and vision, bioinformatics, robotics and manufacturing. Processing geometric data in these applications is challenging, because this data is typically huge, measured with uncertainty, obtained in a distributed manner (e.g., in sensor networks), or in an online manner (e.g., in streaming applications), and may involve moving points (e.g., in imaging, animation and modeling). All these traits make the processing a rather demanding task, and call for the design of novel algorithmic techniques for handling it efficiently. For many of these problems, exact algorithms, even polynomial in the input size, are impractical, and approximation algorithms are needed. Even then, making these algorithms depend efficiently on the error parameter is often a difficult and challenging task.The project addresses the above challenges by developing general algorithmic techniques such as computing geometric summaries (including coresets and random samples), handling noisy geometric data under various probabilistic models of uncertainty, handling online data, and handling kinetic data (involving moving objects). Some of the specific problems that are targeted include shape matching, clustering, and geometric searching. Each of these topics raises interesting algorithmic questions, both theoretical and practical, and the project will address as many of them as possible.