On counting point-hyperplane incidences

DOI10.1016/S0925-7721(02)00127-XzbMath1022.65021OpenAlexW2130760369MaRDI QIDQ1873152

Christian Knauer, Peter Brass

Publication date: 19 May 2003

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(02)00127-x

zbMATH Keywords

lower boundsbipartite subgraph compressionHopcroft's problempoint-hyperplane incidence structure

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (13)

Two theorems on point-flat incidences ⋮ A semi-algebraic version of Zarankiewicz's problem ⋮ Concentration estimates for algebraic intersections ⋮ No l Grid-Points in Spaces of Small Dimension ⋮ On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space ⋮ The polynomial method over varieties ⋮ On a Question of Bourgain about Geometric Incidences ⋮ Covering lattice points by subspaces and counting point-hyperplane incidences ⋮ A bichromatic incidence bound and an application ⋮ On the number of incidences between points and planes in three dimensions ⋮ How to find groups? ⋮ The largest complete bipartite subgraph in point-hyperplane incidence graphs ⋮ Representation Complexities of SemiAlgebraic Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• Update on the no-three-in-line problem
• Extremal problems in discrete geometry
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• A guided tour of Chernoff bounds
• Combinatorial complexity bounds for arrangements of curves and spheres
• No-three-in-line for seventeen and nineteen
• Progress in the no-three-in-line-problem
• Cutting hyperplanes for divide-and-conquer
• Some advances in the no-three-in-line problem
• On the no-three-in-line problem
• Implicitly representing arrangements of lines or segments
• Norm-graphs: Variations and applications
• Can visibility graphs be represented compactly?
• Progress in the no-three-in-line problem. II
• New lower bounds for Hopcroft's problem
• Clique partitions, graph compression and speeding-up algorithms
• The exact fitting problem in higher dimensions
• Efficient algorithms for approximating polygonal chains
• Norm-graphs and bipartite Turán numbers
• Space-Time Tradeoffs for Emptiness Queries
• The No-Three-In-Line Problem
• Covering lattice points by subspaces

This page was built for publication: On counting point-hyperplane incidences