On counting point-hyperplane incidences
From MaRDI portal
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.
Recommendations
Cites work
- A guided tour of Chernoff bounds
- Can visibility graphs be represented compactly?
- Clique partitions, graph compression and speeding-up algorithms
- Combinatorial complexity bounds for arrangements of curves and spheres
- Covering lattice points by subspaces
- Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
- Cutting hyperplanes for divide-and-conquer
- Efficient algorithms for approximating polygonal chains
- Extremal problems in discrete geometry
- scientific article; zbMATH DE number 3841905 (Why is no real title available?)
- scientific article; zbMATH DE number 863486 (Why is no real title available?)
- Implicitly representing arrangements of lines or segments
- New lower bounds for Hopcroft's problem
- No-three-in-line for seventeen and nineteen
- Norm-graphs and bipartite Turán numbers
- Norm-graphs: Variations and applications
- On the no-three-in-line problem
- Progress in the no-three-in-line problem. II
- Progress in the no-three-in-line-problem
- Range searching with efficient hierarchical cuttings
- Some advances in the no-three-in-line problem
- Space-Time Tradeoffs for Emptiness Queries
- The exact fitting problem in higher dimensions
- The No-Three-In-Line Problem
- Update on the no-three-in-line problem
Cited in
(31)- Counting facets and incidences
- Depth in an arrangement of hyperplanes
- The probability that the number of points on a complete intersection is squarefree
- Covering lattice points by subspaces and counting point-hyperplane incidences
- On the number of incidences between points and planes in three dimensions
- New lower bounds for Hopcroft's problem
- Counting problems relating to a theorem of Dirichlet
- The polynomial method over varieties
- How to find groups?
- The largest complete bipartite subgraph in point-hyperplane incidence graphs
- A semi-algebraic version of Zarankiewicz's problem
- scientific article; zbMATH DE number 4213491 (Why is no real title available?)
- Incidences
- INCIDENCE CONSTRAINTS: A COMBINATORIAL APPROACH
- No l Grid-Points in Spaces of Small Dimension
- On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space
- On a Question of Bourgain about Geometric Incidences
- Covering lattice points by subspaces and counting point-hyperplane incidences
- Representation complexities of semialgebraic graphs
- Concentration estimates for algebraic intersections
- A bichromatic incidence bound and an application
- Minkowski's successive minima in convex and discrete geometry
- Discrete geometry. Abstracts from the workshop held January 21--26, 2024
- Evasive sets, covering by subspaces, and point-hyperplane incidences
- Semi-algebraic off-line range searching and biclique partitions in the plane
- Covering points by hyperplanes and related problems
- Semi-algebraic off-line range searching and biclique partitions in the plane
- A note on the no-(d+2)-on-a-sphere problem
- Compact representation of semilinear and terrain-like graphs
- On subsets of lattice cubes avoiding affine and spherical degeneracies
- Two theorems on point-flat incidences
This page was built for publication: On counting point-hyperplane incidences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1873152)
