A bichromatic incidence bound and an application

DOI10.1007/S00454-011-9367-3zbMATH Open1254.52011arXiv1006.3878OpenAlexW3098775666MaRDI QIDQ650111FDOQ650111

Authors: Ben Lund, George B. Purdy, Justin W. Smith 

Publication date: 25 November 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O_d(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2} + m) incidences between the k red points and m hyperplanes spanned by all n points provided that m = Omega(n^{d-2}). For the monochromatic case k = n, this was proved by Agarwal and Aronov. We use this incidence bound to prove that a set of n points, no more than n-k of which lie on any plane or two lines, spans Omega(nk^2) planes. We also provide an infinite family of counterexamples to a conjecture of Purdy's on the number of hyperplanes spanned by a set of points in dimensions higher than 3, and present new conjectures not subject to the counterexample.

Full work available at URL: https://arxiv.org/abs/1006.3878

Recommendations

• scientific article; zbMATH DE number 4213491
• On counting point-hyperplane incidences
• Incidences between points and circles in three and higher dimensions
• Incidences between points and lines in \({\mathbb {R}}^4\)
• Incidences with curves in \(\mathbb{R}^d\)

zbMATH Keywords

hyperplane arrangementconjecture of Purdyincidence boundBeck-Erdős type theorem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cites Work

• Research Problems in Discrete Geometry
• Title not available (Why is that?)
• On the combinatorial problems which I would most like to see solved
• Title not available (Why is that?)
• COLLINEARITY PROPERTIES OF SETS OF POINTS
• Title not available (Why is that?)
• The complexity of many cells in arrangements of planes and related problems
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• Extremal problems in discrete geometry
• On some problems of elementary and combinatorial geometry
• The Lines and Planes Connecting the Points of a Finite Set
• A proof of a consequence of Dirac's conjecture
• Incidences of not-too-degenerate hyperplanes
• Two results about points, lines and planes
• A Generalization of a Theorem of Sylvester on the Lines Determined by a Finite Point Set.
• Counting facets and incidences
• On counting point-hyperplane incidences
• Title not available (Why is that?)

Cited In (8)

• On counting point-hyperplane incidences
• Two theorems on point-flat incidences
• Incidences between planes over finite fields
• An upper bound on the \(k\)-modem illumination problem
• Extending Erdős-Beck's theorem to higher dimensions
• Consistent sets of lines with no colorful incidence
• A theorem about vectors in \(\mathbb{R}^2\) and an algebraic proof of a conjecture of Erdős and Purdy
• Incidences of not-too-degenerate hyperplanes

This page was built for publication: A bichromatic incidence bound and an application

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650111)