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.