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.