On counting point-hyperplane incidences

AbstractIn this paper we discuss three closely related problems on the incidence structure between n points and m hyperplanes in d-dimensional space: the maximal number of incidences if there are no big bipartite subconfigurations, a compressed representation for the incidence structure, and a lower bound for any algorithm that determines the number of incidences (counting version of Hopcroft's problem). For this we give a construction of a special point-hyperplane configuration, giving a lower bound, which almost meets the best upper bound known thus far