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.
