The analysis of substructures in geometric arrangements received considerable attention in the past twenty years. Informally, an arrangement of a set of geometric objects in $d$-space is the subdivision of space that they induce, and a substructure in the arrangement is a collection of certain features of the arrangement.
Arrangements have emerged as the underlying structure of geometric problems in a variety of applications, such as robot motion planning, pattern matching, visibility problems in computer graphics and modeling, geographic information systems, bioinformatics, and more. In addition, they arise in most of the basic problems in computational geometry.
It is well known that the combinatorial complexity of the entire arrangement of $n$ simply-shaped objects in $d$-space is $\Theta(n^d)$ in the worst case. However, there are various applications where one is only interested in parts of the arrangement, such as a single cell of the arrangement, or the boundary of the union of geometric objects. The hope is that substructures in arrangements should have smaller complexity than that of the full arrangement, and that therefore one should be able to compute them more efficiently.
In this talk I will survey some of the fundamental results concerning union of geometric objects in 2- and 3-dimensions. I will then present a nearly-optimal bound for the union of "fat" tetrahedra in 3-space.
Joint work with Micha Sharir, Tel-Aviv university.