The complexity of many cells in arrangements of planes and related problems (Q582901)

The techniques developed in a companion paper by the same authors are extended to problems involving arrangements of planes in three dimensions or hyperplanes in higher dimensions. The problems are decomposed into subproblems of smaller size, random sampling and \(\epsilon\)-nets are used. The complexity of many cells in arrangements of planes in three dimensions is analyzed and an efficient worst-case algorithm for their calculation is presented. Also the following simpler problems are studied: Count the maximum number of incidences between planes and vertices of their arrangement (a randomized algorithm for their calculation is given); obtain an upper bound on the number of incidences between these points and planes, assuming that no three points are collinear; determine for each of given m points the plane of a given set of planes lying immediately below it. Count the maximum number of facets bounding m distinct cells in an arrangement of n hyperplanes in d dimensions \((d>3)\).