On counting point-hyperplane incidences
type: Item
instance of: scholarly article
title: On counting point-hyperplane incidences
zbMATH Open document ID: 1022.65021
DOI: 10.1016/S0925-7721(02)00127-X
author: Christian Knauer
author: Peter Brass
published in: Computational Geometry
publication date: 2003-05-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 1912420
zbMATH Keywords: point-hyperplane incidence structure
zbMATH Keywords: bipartite subgraph compression
zbMATH Keywords: lower bounds
zbMATH Keywords: Hopcroft's problem
reviewed by: Francisco Pérez Acosta
MaRDI profile type: Publication
cites work: Efficient algorithms for approximating polygonal chains
cites work: Can visibility graphs be represented compactly?
cites work: Norm-graphs: Variations and applications
cites work: Update on the no-three-in-line problem
cites work: Covering lattice points by subspaces
cites work: Cutting hyperplanes for divide-and-conquer
cites work: Q3312268
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: On the no-three-in-line problem
cites work: Implicitly representing arrangements of lines or segments
cites work: Q4871765
cites work: New lower bounds for Hopcroft's problem
cites work: Space-Time Tradeoffs for Emptiness Queries
cites work: Clique partitions, graph compression and speeding-up algorithms
cites work: Progress in the no-three-in-line-problem
cites work: Progress in the no-three-in-line problem. II
cites work: The exact fitting problem in higher dimensions
cites work: The No-Three-In-Line Problem
cites work: A guided tour of Chernoff bounds
cites work: Some advances in the no-three-in-line problem
cites work: No-three-in-line for seventeen and nineteen
cites work: Norm-graphs and bipartite Turán numbers
cites work: Range searching with efficient hierarchical cuttings
cites work: Extremal problems in discrete geometry
cites work: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
full work available at URL: s0925-7721(02)00127-x
OpenAlex ID: W2130760369
description: scientific article; zbMATH DE number 1912420