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.
|Effective start/end date||9/15/09 → 8/31/12|
- National Science Foundation (National Science Foundation (NSF))