A bichromatic incidence bound and an application

DOI10.1007/S00454-011-9367-3MaRDI QIDQ650111zbMATH OpenOpenAlexFDO

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

Publication date 25 November 2011

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

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

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)

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.

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\)

Cites work

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

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)