AF:EAGER: Combinatorial Geometry, Partitioning, and Algorithms

分治法和剪枝搜索法是算法设计中两种基本且普遍存在的范式。第一个是指(i)将给定的问题分解成更小的子问题，（ii）求解每个子问题，然后（iii）将这些解组合起来得到原始问题的解。第二种是在给定问题的可能解决方案中搜索的方法，其中(a)将可能的解决方案分成几组，然后(b)以某种方式排除除一组外的所有组，最后(c)继续搜索，现在仅限于剩下的一组。值得注意的是，在这两种方法中，集合都被“分割”成更小的集合——分治的步骤(i)和剪枝搜索的步骤(a)——此外，许多高效而美观的算法都是基于这些方法中的一种。这个项目的主要目标是开发一些不同寻常的、新的、可以在这些范例中使用的拆分工具。它们将从一个意想不到的领域——几何分划定理中寻找。拓扑方法已经被应用于获得像火腿三明治定理这样的事实，但是在它们的算法方面还没有太多的工作，我们所得到的结果表明，它们作为其他算法的分割工具不是很有用。然而，研究者最近的一些划分结果鼓励人们寻找更多这类工具。因此，这项工作将继续寻求新的几何划分结果，可以提供新颖，有用的分裂工具。同时，该项目将解决一组具体的、顽固的计算问题，这些问题经常出现，而且很自然，但迄今为止还没有有效的解决方案。我们的目标是更好地理解这些重要而有趣的问题的复杂性，并应用新的工具来获得有效的算法。该项目的部分智力价值在于开发新算法工具的不同寻常的方法；此外，还有机会在一系列普遍的、困难的计算问题上取得进展。更广泛的影响在于有可能加强几何、组合学和计算之间的联系。

Divide-and-conquer and prune-and-search are two fundamental and ubiquitous paradigms in the design of algorithms. The first refers to the process of (i) splitting a given problem into smaller sub-problems, (ii) solving each of these subproblems, and then (iii) combining these solutions to obtain the solution to the original problem. The second is a way of searching among possible solutions to a given problem whereby (a) the possible solutions are split into several groups, then (b) all but one of the groups is somehow eliminated, and finally (c) the search continues, now confined to the one remaining group. It is noteworthy that in both approaches, sets are ``split'' into smaller ones - step (i) in divide-and conquer and step (a) in prune-and-search - and that in addition, many efficient and beautiful algorithms are based on one of these approaches. A main goal of this project is the development of some unusual, new, splitting tools that may be used in these paradigms. They will be sought from within an unexpected domain - geometric partitioning theorems. Topological methods have been applied to obtain facts like the ham-sandwich theorem, but there has not been much work on their algorithmic aspects, and what results we do have suggest that they would not be very useful as splitting tools for other algorithms. However some recent partitioning results of the investigator encourage the search for more tools of this kind.Therefore this work will continue to seek new geometric partitioning results that can give novel, useful, splitting tools. Simultaneously the project will address a specific set of concrete, stubborn computational problems that arise frequently, and naturally, but have so far resisted efficient solutions. The goal is to better understand the complexity of these important and interesting problems, and to apply the new tools to obtain effective algorithms. Part of the intellectual merit of the project rests on the unusual approach to develop new algorithmic tools; in addition there is chance to make progress on a set of prevalent, hard, computational problems. Broader impacts reside in the potential to strengthen connections between geometry, combinatorics, and computation.