EXTREMAL PROBLEMS FOR GEOMETRIC HYPERGRAPHS

A geometric hypergraph H is a collection of i-dimensional simplices, c alled hyperedges or, simply, edges, induced by some (i + I)-tuples of a vertex set V in general position in d-space. The topological structu re of geometric graphs, i.e., the case d = 2, i = i, has been studied extensively, and it proved to be instrumental for the solution of a wi de range of problems in combinatorial and computational geometry. They include the k-set problem, proximity questions, bounding the number o f incidences between points and lines, designing various efficient gra ph drawing algorithms, etc. In this paper, we make an attempt to gener alize some of these tools to higher dimensions. We will mainly conside r extremal problems of the following type. What is the largest number of edges (i-simplices) that a geometric hypergraph of n vertices can h ave without containing certain forbidden configurations? In particular , we discuss the special cases when the forbidden configurations are k intersecting edges, k pairwise intersecting edges, k crossing edges, k pairwise crossing edges, k edges that can be stabbed by an i-flat, e tc. Some of our estimates are tight.