Chiu, ManKwun ;
Choudhary, Aruni ;
Mulzer, Wolfgang
Computational Complexity of the αHamSandwich Problem
Abstract
The classic HamSandwich 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 wellseparated, 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 αHamSandwich theorem. They gave an algorithm to find the hyperplane in time O(n (log n)^{d3}), 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 HamSandwich problem, which is now known to be PPAcomplete (FilosRatsikas and Goldberg [STOC 2019]).
Recently, Fearnley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new subclass of CLS (Continuous Local Search) called Unique EndofPotential Line (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the αHamSandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first nontrivial 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 Pmatrix linear complementarity problem.
BibTeX  Entry
@InProceedings{chiu_et_al:LIPIcs:2020:12438,
author = {ManKwun Chiu and Aruni Choudhary and Wolfgang Mulzer},
title = {{Computational Complexity of the αHamSandwich Problem}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {31:131:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12438},
URN = {urn:nbn:de:0030drops124382},
doi = {10.4230/LIPIcs.ICALP.2020.31},
annote = {Keywords: HamSandwich Theorem, Computational Complexity, Continuous Local Search}
}
29.06.2020
Keywords: 

HamSandwich Theorem, Computational Complexity, Continuous Local Search 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 