On counting point-hyperplane incidences (Q1873152)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On counting point-hyperplane incidences |
scientific article |
Statements
On counting point-hyperplane incidences (English)
0 references
19 May 2003
0 references
The authors 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 determine the number of incidences. For this a construction of a special point-hyperplane configuration is presented. A lower bound is given, which almost meets the best upper bound known thus far.
0 references
point-hyperplane incidence structure
0 references
bipartite subgraph compression
0 references
lower bounds
0 references
Hopcroft's problem
0 references
