2025/03/20 by Sebastian Haslebacher, Jonas F. Lill, Haslebacher, Sebastian +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2503.16089
openalex publication_date 2025/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that an ε-approximate fixpoint of a map f:[0,1]d→ [0,1]d can be found with O(d2(log\frac1ε + log(1)/(1-λ))) queries to f if f is λ-contracting with respect to an ℓp-metric for some p∈ [1,∞)∪\∞\. This generalizes a recent result of Chen, Li, and Yannakakis [STOC'24] from the ℓ_∞-case to all ℓp-metrics. Previously, all query upper bounds for p∈ [1,∞) ∖ \2\ were either exponential in d, log\frac1ε, or log(1)/(1-λ). Chen, Li, and Yannakakis also show how to ensure that all queries to f lie on a discrete grid of limited granularity in the ℓ_∞-case. We provide such a rounding for the ℓ1-case, placing an appropriately defined version of the ℓ1-case in \textsfFPdt. To prove our results, we introduce the notion of ℓp-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any p ∈ [1, ∞) ∪ \∞\ and any mass distribution (or point set), we prove that there exists a centerpoint c such that every ℓp-halfspace defined by c and a normal vector contains at least a (1)/(d+1)-fraction of the mass (or points).