Complexity of 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.