2021/06/09 by Brett Leroux, Leroux, Brett, Luis Rademacher +1 · 1 citation
Computer Science · Mathematics · #05C30 #52C05 #52C10 #60D05 #68Q25 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematical Approximation and Integration #Metric Geometry (math.MG) #Point processes and geometric inequalities #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2106.04782
openalex publication_date 2021/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finite set of points S⊂ℝd, a k-set of S is a subset A ⊂ S of size k which can be strictly separated from S ∖ A by a hyperplane. Similarly, a k-facet of a point set S in general position is a subset Δ⊂ S of size d such that the hyperplane spanned by Δ has k points from S on one side. For a probability distribution P on ℝd, we study EP(k,n), the expected number of k-facets of a sample of n random points from P. When P is a distribution on ℝ2 such that the measure of every line is 0, we show that EP(k,n) = O(n(k+1)1/4). Our argument is based on a technique by Bárány and Steiger. We study how it may be possible to improve this bound using the continuous version of the polynomial partitioning theorem. This motivates a question concerning the points of intersection of an algebraic curve and the k-edge graph of a set of points. We also study a variation on the k-set problem for the set system whose set of ranges consists of all translations of some strictly convex body in the plane. The motivation is to show that the technique by Bárány and Steiger is tight for a natural family of set systems. For any such set system, we determine bounds for the expected number of k-sets which are tight up to logarithmic factors.