Fast enumeration of point hyperplane incidences
Peter Braß, Christian Knauer · 2000
In this paper we study the complexity of enumerating all incidences between a set of n points P and a set of m hyperplanes H in d-dimensional euclidean space R d . We describe a deterministic algorithm that computes an encoding of all point-hyperplane incidences between P and H in O (m + n) log(m + n) + (mn) d d+1 (log(mn)) d time, where d is an appropriate constant of order O(d log d). The encoding we use is a covering of the incidence graph with complete bipartite subgraphs. We complement our algorithm with a construction that yields m+ n +m d 2d 1 n 2d 2 2d 1 +m 2d 2 2d 1 n d 2d 1 incidences that can not be encoded eciently. Keywords: Computational geometry, Cuttings, Hopcroft's problem, Point-hyperplane incidences. 1 Introduction Determining the incidences between a set of points and a set of lines, or curves, or hyperplanes, is an important step in some algorithms. For n points and m lines it is well known that there are at most O m+n+m 2 3 n 2 3 ...