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.