2015/03/31 by Mikio Kano, Jan Kynčl · 3 citations
Computer Science · Mathematics · #Absolute continuity #Closed set #Computational Geometry and Mesh Generation #Disjoint sets #Hyperplane #Limits and Structures in Graph Theory #Open set #Point processes and geometric inequalities #Set (abstract data type) #math.CO #math.MG #msc:28A75 #msc:52C35
paper · pdf · doi:10.1016/j.comgeo.2017.06.012
published in Computational Geometry 68, 167-173 (Elsevier BV) · 11 pages, 2 figures; a new proof of Theorem 8, extended concluding remarks
openalex created_date 2016/06/24 · openalex publication_date 2017/07/03 · arxiv created 2018/12/16 · arxiv updated 2018/12/18 · openalex updated_date 2026/08/06
We generalize the ham sandwich theorem to d+1 measures in ℝd as follows. Let μ1,μ2, …, μd+1 be absolutely continuous finite Borel measures on ℝd. Let ωi=μi(ℝd) for i∈ [d+1], ω=min\ωi; i∈ [d+1]\ and assume that ∑j=1d+1 ωj=1. Assume that ωi ≤ 1/d for every i∈[d+1]. Then there exists a hyperplane h such that each open halfspace H defined by h satisfies μi(H) ≤ (∑j=1d+1 μj(H))/d for every i ∈ [d+1] and ∑j=1d+1 μj(H) ≥ min(1/2, 1-dω) ≥ 1/(d+1). As a consequence we obtain that every (d+1)-colored set of nd points in ℝd such that no color is used for more than n points can be partitioned into n disjoint rainbow (d-1)-dimensional simplices.