论文标题
$α$ -HAM-SANDWICH问题的计算复杂性
Computational Complexity of the $α$-Ham-Sandwich Problem
论文作者
论文摘要
经典的ham-sandwich定理指出，对于任何$ d $的可测量集，均以$ \ mathbb {r}^d $为单位，有一个超平面，可以同时将它们分为二。 Bárány，Hubard和Jerónimo[DCG 2008]的延伸指出，如果这些集合是凸出的，并且\ emph {emph {apprepareated}，那么对于任何给定的$α_1，\ dots，α_d\ inα_d\ in [0，1] $，每个$ n.plantimentiment Entranient from $ $ naw_ $ nave $ natiment $ a $ nive $ nistive native native nabl y ractive naw $ nistive。 放。 Steiger and Zhao [DCG 2010]证明了该定理的离散类似物，我们称之为\ emph {$α$ -Ham-sandwich定理}。他们给出了一种算法，以在时间$ o（n（\ log n）^{d-3}）$中找到超平面，其中$ n $是输入点的总数。该搜索问题在高维度上的计算复杂性是开放的，这与Ham-Sandwich问题的复杂性完全不同，Ham-Sandwich问题的复杂性现在已知是PPA完整的（Filos-Ratsikas and Goldberg [Stoc 2019]）。 最近，Fearley，Gordon，Mehta和Savani [ICALP 2019]推出了一个新的CLS子类（连续的本地搜索），称为\ EMPH {唯一的终端电位线}（UEOPL）。该课程捕获具有独特解决方案的CL中的问题。我们表明，对于$α$ -HAM-SANDWICH定理，查找分裂超平面位于UEOPL的搜索问题。这给出了复杂性类别中问题的第一个非平凡遏制，并将其置于经典搜索问题的公司中，例如查找收缩图的固定点，独特的下沉方向问题以及$ p $ -Matrix线性互补性问题。
The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $\mathbb{R}^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 \emph{well-separated}, then for any given $α_1, \dots, α_d \in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $α_1, \dots, α_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the \emph{$α$-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, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called \emph{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.
