Stabbing simplices by points and flats

DOI10.1007/S00454-008-9124-4zbMATH Open1186.52001arXiv0804.4464OpenAlexW3106539039MaRDI QIDQ848667FDOQ848667

Authors: Boris Bukh, Jiří Matoušek, Gabriel Nivasch 

Publication date: 4 March 2010

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

Abstract: The following result was proved by Barany in 1982: For every d >= 1 there exists c_d > 0 such that for every n-point set S in R^d there is a point p in R^d contained in at least c_d n^{d+1} - O(n^d) of the simplices spanned by S. We investigate the largest possible value of c_d. It was known that c_d <= 1/(2^d(d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c_d <= (d+1)^{-(d+1)}, and we conjecture this estimate to be tight. The best known lower bound, due to Wagner, is c_d >= gamma_d := (d^2+1)/((d+1)!(d+1)^{d+1}); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than gamma_d n^{d+1}+O(n^d) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved. We also prove that for every n-point set S in R^d there exists a (d-2)-flat that stabs at least c_{d,d-2} n^3 - O(n^2) of the triangles spanned by S, with c_{d,d-2}>=(1/24)(1- 1/(2d-1)^2). To this end, we establish an equipartition result of independent interest (generalizing planar results of Buck and Buck and of Ceder): Every mass distribution in R^d can be divided into 4d-2 equal parts by 2d-1 hyperplanes intersecting in a common (d-2)-flat.

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

Recommendations

• Stabbing simplices of point sets with \(k\)-flats
• Upper bounds for stabbing simplices by a line
• Hitting simplices with points in \(\mathbb R^{3}\)
• The number of congruent simplices in a point set
• scientific article; zbMATH DE number 763368

zbMATH Keywords

simplexequivariant mapcohomological indexequipartitioncenterpointselection lemmaRado's centerpoint theorem

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Cites Work

• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Title not available (Why is that?)
• A Theorem on General Measure
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Borsuk-Ulam type theorems on Stiefel manifolds
• An ideal-valued cohomological index theory with applications to Borsuk—Ulam and Bourgin—Yang theorems
• User's guide to equivariant methods in combinatorics. II
• A Problem in Geometric Probability.
• The colored Tverberg's problem and complexes of injective functions
• Point Selections and Weak ε-Nets for Convex Hulls
• Improved bounds for intersecting triangles and halving planes
• Counting triangle crossings and halving planes
• On the number of halving planes
• Entering and leaving \(j\)-facets
• A point in many triangles
• Eppstein's bound on intersecting triangles revisited
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (29)

• A proof of the Oja depth conjecture in the plane
• Title not available (Why is that?)
• A center transversal theorem for an improved Rado depth
• Ham-sandwich cuts and center transversals in subspaces
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On Gromov's method of selecting heavily covered points
• Stabbing Delaunay tetrahedralizations
• Upper bounds for stabbing simplices by a line
• Codimension two and three Kneser transversals
• Extremal problems for pairs of triangles
• \(k\)-centerpoints conjectures for pointsets in \(\mathbb{R}^d\)
• Stellar discriminants and equipartitions
• Hitting simplices with points in \(\mathbb R^{3}\)
• Tverberg’s theorem is 50 years old: A survey
• Stabbing simplices of point sets with \(k\)-flats
• Complete Kneser transversals
• Centerpoints and Tverberg's technique
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Intersection theorems for triangles
• A survey of mass partitions
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• A new lower bound based on Gromov's method of selecting heavily covered points
• Hypergraph expanders from Cayley graphs
• One-sided epsilon-approximants
• An elementary exposition of topological overlap in the plane
• An improvement on the Rado bound for the centerline depth
• Homogeneous selections from hyperplanes
• A slight improvement to the colored Bárány's theorem
• Positive-fraction intersection results and variations of weak epsilon-nets

This page was built for publication: Stabbing simplices by points and flats

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