BSF:201229:Efficient Algorithms for Geometric Optimization

该项目是美国-以色列计算机科学合作(USICCS)计划的一部分。通过这一计划，美国国家科学基金会和美国-以色列双国科学基金会(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.