Geometric Complexity Problems in Arrangements

计算几何主要研究几何算法。因此，计算几何学家考虑的问题的几何方面与算法和数据结构方面一样重要。有时，连接是明确的，例如，当几何对象的特征的数量提供了计算它的运行时间的最坏情况下界时。其他时候，这种关系不那么明显，但同样重要。这个项目主要从组合的角度而不是计算的角度来研究几何排列，研究算法问题是次要的目标。重点放在几何复杂性问题上，这涉及到估计排列某些部分的特征数量。这样的组合界导致了高效几何算法的构造，并为它们的性能建立了精确的下界。各类物体的平面排列和一般超平面排列已被广泛研究，但直到最近，对三维空间中平面三角形等简单物体的排列还知之甚少。在最近一些工作的基础上，将继续对这一主题进行调查，最初集中在三角形安排上。单纯形排列的研究有望导致适用于更一般的三维和更高维对象族的新技术，这反过来将为几何算法的设计和分析提供更好的工具。

Computational Geometry is primarily the study of geometric algorithms. Thus the geometric aspect of problems considered by computational geometers is as important as the algorithm and data structuring aspect. Sometimes the connection is explicit, e.g, when the number of features of a geometric object provides a worst-case lower bound on the running time to compute it. Other times the relation is less obvious, but just as crucial. This project is concerned with geometric arrangements from a primarily combinatorial rather than computational point of view, with investigation of algorithmic issues as a secondary goal. The focus is on the geometric complexity problems, which involve estimating the number of features in certain portions of an arrangement. Such combinatorial bounds lead to construction of efficient geometric algorithms and to establishing sharp lower bounds on their performance. Planar arrangements of various classes of objects and general hyperplane arrangements have been studied extensively, but until recently rather little was known about arrangements of such simple objects as flat triangles in three-dimensional space. Building on some recent work, the investigation of this subject will be continued, initially concentrating on triangle arrangements. The study of simplex arrangements is expected to lead to new techniques applicable to more general families of objects in three and higher dimensions, which will in turn yield better tools for the design and analysis of geometric algorithms.