An Extension of a Theorem of Yao and Yao

2011/12/31 by Edgardo Roldán-Pensado, Pablo Soberón · 4 citations
Computer Science · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Data mining #Digital Image Processing Techniques #Discrete mathematics #Extension (predicate logic) #Hyperplane #Integer (computer science) #Limits and Structures in Graph Theory #Mathematics #Measure (data warehouse) #math.MG

paper · pdf · doi:10.1007/s00454-014-9568-7

published in Discrete & Computational Geometry 51(2), 285-299 (Springer Science+Business Media)

arxiv created 2012/04/06 · openalex publication_date 2014/01/15 · openalex created_date 2016/06/24 · arxiv updated 2021/06/09 · openalex updated_date 2026/08/05

Abstract

In this paper we study N_d(k) the smallest positive integer such that any nice measure μ in \R^d can be partitioned in N_d(k) parts of equal measure so that every hyperplane avoids at least k of them. A theorem of Yao and Yao \citeYY1985 states that N_d(1) ≤ 2^d. Among other results, we obtain the bounds N_d(2) ≤ 3 ⋅ 2^d-1 and N_d(1) ≥ C ⋅ 2^d/2 for some constant C. We then apply these results to a problem on the separation of points and hyperplanes.

Citations

• Using the Borsuk–Ulam Theorem
• BALANCED CONVEX PARTITIONS OF MEASURES IN ℝ d
• The dimension of almost spherical sections of convex bodies