2026-07-27T17:10:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12438 2024-03-06T10:50:08Z ddc:004 open_access

Computational Complexity of the α-Ham-Sandwich Problem Chiu, Man-Kwun Choudhary, Aruni Mulzer, Wolfgang Ham-Sandwich Theorem Computational Complexity Continuous Local Search The classic Ham-Sandwich theorem states that for any d measurable sets in ℝ^d, there is a hyperplane that bisects them simultaneously. An extension by Bárány, Hubard, and Jerónimo [DCG 2008] states that if the sets are convex and well-separated, then for any given α₁, … , α_d ∈ [0, 1], there is a unique oriented hyperplane that cuts off a respective fraction α₁, … , α_d from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the α-Ham-Sandwich theorem. They gave an algorithm to find the hyperplane in time O(n (log n)^{d-3}), where n is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearnley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called Unique End-of-Potential Line (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the α-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the P-matrix linear complementarity problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Man-Kwun Chiu and Aruni Choudhary and Wolfgang Mulzer 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.31 urn:nbn:de:0030-drops-124382 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.31 eng https://creativecommons.org/licenses/by/3.0/legalcode