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.
