AF: Small: Geometric Optimization via Combinatorial Geometry

AF：小：通过组合几何进行几何优化

• 批准号: 1216689
• 负责人: Richard Cole
• 金额: $ 24.26万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-15 至 2014-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216689&HistoricalAwards=false
• 关键词: AF; Small; Geometric; Optimization; via

The goal of this project is to consider classical optimization problems, originally stated in the context of abstract graph theory and combinatorial optimization, whose hardness as well as approximation factors have been studied extensively, and investigate them in a geometric context, that is, when the input consists of geometric objects. While considerable progress has been made on the analysis of such problems in the abstract setting, their geometric variants have received much less attention. These problems include minimum coverage of a given area, stabbing a set of geometric objects, geometric packing, and obtaining largest sets of mutually intersecting geometric objects. For each of these problems, new ideas will be explored, which aim to combine tools from computational and combinatorial geometry with traditional algorithmic tools from theoretical computer science. Specifically, this work exploits techniques such as linear programming relaxation and local search, commonly used in operation research, combinatorial optimization, and algorithm theory, with tools from computational and combinatorial geometry such as geometric arrangements, Epsilon-nets, Helly-type properties, and others.This award will help to develop a new set of tools that will not only be exploited in computational and combinatorial geometry, but will extend to other (perhaps, more applied) disciplines, such as networking, computer graphics, geographic information systems, learning and others, as they often pose problems of geometric nature. In particular, each of the problems to be investigated in this project has applications to these areas, and hence their importance is not only theoretical but also practical. The project will support and train one postdoctoral researcher in Computer Science at NYU. The PI will disseminate the research to the scientific community through conference and journal publications, teaching courses, as well as presenting her works in departmental seminars, and collaboration with researchers from various disciplines.

这个项目的目标是考虑经典的优化问题，最初是在抽象图论和组合优化的背景下提出的，其硬度以及近似因子已经被广泛研究，并在几何背景下研究它们，即当输入由几何对象组成时。 虽然已经取得了相当大的进展，在分析这些问题的抽象设置，他们的几何变体得到了较少的关注。这些问题包括给定区域的最小覆盖范围、插入一组几何对象、几何包装以及获得最大的相交几何对象集。对于这些问题中的每一个，都将探索新的想法，其目的是将计算和组合几何学的联合收割机工具与理论计算机科学的传统算法工具相结合。具体而言，这项工作利用了线性规划松弛和局部搜索等技术，这些技术通常用于运筹学，组合优化和算法理论，并使用了计算和组合几何的工具，如几何排列，Epsilon网，Helly-type属性等。该奖项将有助于开发一套新的工具，不仅用于计算和组合几何，但将扩展到其他（也许是更应用的）学科，如网络、计算机图形、地理信息系统、学习和其他学科，因为它们经常提出几何性质的问题。特别是，在这个项目中要调查的每一个问题都适用于这些领域，因此它们的重要性不仅是理论上的，而且是实际的。 该项目将支持和培训一名纽约大学计算机科学博士后研究员。PI将通过会议和期刊出版物，教学课程，以及在部门研讨会上展示她的作品，并与来自不同学科的研究人员合作，向科学界传播研究成果。