Complexity of geometric arrangements

几何排列的复杂性

• 批准号: 329257-2006
• 负责人: Tardos, Gabor
• 金额: $ 2.19万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=398113
• 关键词: Complexity; geometric; arrangements

Arrangement of simple geometric shapes (lines, triangles, hyperplanes) can lead to very complex arrangements. The complexity of many geometric algorithms crucially depend on the complexity of the these arrangements, therefore it is important to understand what requirements ensure a bound on the complexity of the arrangements and therefore on the running time of certain algorithms. In certain computational or combinatorial problems that are seemingly not geometric in nature, for example in some optimization problems, one can represent the data in as an arrangement of surfaces or other shapes and apply geometric arguments in the solution. The proposed research is a continuation on similar research carried out by myself and other researchers on complexity of geometric arrangements. We propose for example to extend results about the complexity of the union of fat objects from two to higher dimensions. Geometric graphs proved to be very useful in modeling spatial arrangements and relations. We propose to work on the extremal theory of geometric graphs and related theory of ordered graphs.

简单几何形状（直线、三角形、超平面）的排列可以导致非常复杂的排列。许多几何算法的复杂性主要取决于这些安排的复杂性，因此，重要的是要了解什么要求确保对安排的复杂性的约束，从而对某些算法的运行时间。在某些计算或组合问题，似乎不是几何的性质，例如在一些优化问题，可以表示的数据作为一个安排的表面或其他形状和应用几何参数的解决方案。本文的研究是本人和其他研究者对几何排列复杂性的类似研究的继续。例如，我们建议扩展结果的复杂性的工会的脂肪对象从两个更高的维度。几何图形被证明是非常有用的建模空间安排和关系。我们打算研究几何图的极值理论和有序图的相关理论。