Computational Complexity of Geometric and Combinatorial Problems

拟议研究的主要目标是加深我们对一些基本组合和几何问题固有的计算复杂性的理解。这将通过对以下问题提供定性和定量的答案来实现：(I)“某些特征(特定问题实例的属性或解决这些问题的计算框架的属性)以什么方式和在多大程度上有助于解决特定家庭中的问题的内在困难？”及其补充(Ii)“我们可以用什么方式和在多大程度上利用某些自然产生的特征或约束，或修改计算框架，以便为这些问题的实际实例提供更有效的解决方案？”*我们建议解决的许多问题涉及运动中的对象，其有效解决方案需要清楚地了解连续几何约束与对象和环境的离散组合属性之间的相互作用。我们将解决简单机器人在各种运动/环境约束下的路径规划问题的具体问题，提供了具体的例子，这些问题的区别在于它们在广泛的各种应用中所发挥的基本作用。因此，它们为在上述第二个问题上取得有意义的进展提供了肥沃的土壤。然而，这些问题可以，也应该被视为类似结构问题的更广泛家族的代表。在这个意义上，从更多的理论角度来看，它们有助于在第一个问题上取得进展。最终，我们的成功应该以新技术来衡量，用于设计和分析有效的算法和数据结构，并识别适用于最一般情况的内在复杂性限制。*我们的方法论涉及(I)仔细选择问题(考虑到我们的实际和理论影响的双重目标)，(Ii)一方面识别和利用算法和数据结构设计任务之间的关键相互作用，另一方面为现实的计算模型制定复杂性下限，以及(Iii)对实际问题的敏感性(包括高效的，通常是自适应的，算法和健壮的实现)以及理论考虑(包括渐近最优性、难度和完备性结果，以及其他依赖于模型的问题)。*要有效地实现该研究计划，需要考虑和利用替代的计算模型(包括顺序、并行、分布式和随机模型)，注意结构和资源的权衡，以及在设计和分析算法和高级数据结构时利用/增强其他已有的技术和结果。

The primary objective of the proposed research is to further our understanding of the inherent computational complexity of a number of fundamental combinatorial and geometric problems. This will be achieved by providing qualitative and quantitative answers to the questions: (i) "In what ways and to what extent do certain features (attributes of specific problem instances, or of the computational framework in which they are being addressed) contribute to the intrinsic difficulty of solving problems in a particular family?" and its complement (ii) "In what ways and to what extent can we exploit certain naturally occurring features or constraints, or modify the computational framework, to provide more efficient solutions to practical instances of these problems?"****Many of the problems that we propose to address involve objects in motion, and their effective solution requires a clear understanding of the interplay between continuous geometric constraints and the discrete combinatorial attributes of the objects and environment. Specific problems that we will address path-planning problems for simple robots, under various motion/environment constraints, provide concrete examples are distinguished by the fundamental role that they play in a wide variety of applications. As such they provide fertile ground for meaningful progress on the second of the questions above. However, the problems can, and should, also be viewed as representatives of broader families of similarly structured problems. In this sense they facilitate, from a more theoretical standpoint, progress on the first question. Ultimately, our success should be measured in terms of new techniques for the design and analysis of efficient algorithms and data structures, and for the identification of inherent complexity limitations that apply in the most general possible context.******Our methodology involves (i) the careful selection of problems (bearing in mind our dual objectives of practical and theoretical impact), (ii) the identification and exploitation of the critical interplay between tasks of algorithm and data structure design, on one hand, and the formulation of lower bounds on complexity for realistic models of computation on the other, and (iii) a sensitivity for practical issues (including efficient, often adaptive, algorithms together with robust implementations) as well as theoretical considerations (including asymptotic optimality, hardness and completeness results, and other model-dependent concerns).******To be effectively realized this research program requires consideration and utilization of alternative models of computation (including sequential, parallel, distributed and randomized models), attention to structural and resource trade-offs, and the exploitation/enhancement of other established techniques and results in both the design and analysis of algorithms and advanced data structures.***********