Computational aspects of the colorful Carathéodory theorem

DOI10.1007/S00454-018-9979-YMaRDI QIDQ1991350zbMATH OpenOpenAlexFDO

Authors Wolfgang Mulzer, Yannik Stein

Publication date 30 October 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3347

zbMATH Keywords

approximationcolorful Carathéodory theoremPLS

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Let $C_1,dots,C_{d+1}subsetmathbb{R}^d$ be $d+1$ point sets, each containing the origin in its convex hull. We call these sets color classes, and we call a sequence $p_1,dots,p_{d+1}$ with $p_{i}in{C}_i$, for $i=1,dots,d+1$, a colorful choice. The colorful Carath'eodory theorem guarantees the existence of a colorful choice that also contains the origin in its convex hull. The computational complexity of finding such a colorful choice (CCP) is unknown. This is particularly interesting in the light of polynomial-time reductions from several related problems, such as computing centerpoints, to CCP. We define a novel notion of approximation that is compatible with the polynomial-time reductions to CCP: a sequence that contains at most $k$ points from each color class is called a $k$-colorful choice. We present an algorithm that for any fixed $varepsilon>0$, outputs an $lceilepsilondceil$-colorful choice containing the origin in its convex hull in polynomial time. Furthermore, we consider a related problem of CCP: in the nearest colorful polytope problem (NCP), we are given sets $C_1,dots,C_{n}subsetmathbb{R}^d$ that do not necessarily contain the origin in their convex hulls. The goal is to find a colorful choice whose convex hull minimizes the distance to the origin. We show that computing a local optimum for NCP is PLS-complete, while computing a global optimum is NP-hard.

Recommendations

• scientific article; zbMATH DE number 6789180
• The rainbow at the end of the line -- a \textsf{PPAD} formulation of the colorful Carathéodory theorem with applications
• Colorful linear programming, Nash equilibrium, and pivots
• Colourful Linear Programming and its Relatives
• scientific article; zbMATH DE number 1054763

Cites work

• A further generalization of the colourful Carathéodory theorem
• A generalization of Caratheodory's theorem
• A Generalization of Radon's Theorem
• A generalization of Radon's theorem II
• A Theorem on General Measure
• Approximate centerpoints with proofs
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Approximating Tverberg points in linear time for any fixed dimension
• Colorful linear programming, Nash equilibrium, and pivots
• Colourful Linear Programming and its Relatives
• Computing a centerpoint of a finite planar set of points in linear time
• How easy is local search?
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1973378 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• On generalizations of Radon's theorem and the Ham sandwich theorem
• On total functions, existence theorems and computational complexity
• Partitions of points into simplices with k-dimensional intersection. I: The conic Tverberg's theorem
• Simple Local Search Problems that are Hard to Solve
• The complexity of pure Nash equilibria
• The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
• The polynomial solvability of convex quadratic programming
• The rainbow at the end of the line -- a \textsf{PPAD} formulation of the colorful Carathéodory theorem with applications
• Theoretical aspects of local search.
• Time bounds for selection
• Tverberg's theorem via number fields
• Very colorful theorems

Cited in

(10)

• Colorful linear programming, Nash equilibrium, and pivots
• No-dimensional Tverberg theorems and algorithms
• Computing colourful simplicial depth and Median in \(\mathbb{R}_2\)
• Colourful Linear Programming and its Relatives
• The rainbow at the end of the line -- a \textsf{PPAD} formulation of the colorful Carathéodory theorem with applications
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• scientific article; zbMATH DE number 6789180 (Why is no real title available?)
• scientific article; zbMATH DE number 6724468 (Why is no real title available?)
• Computational complexity of the -Ham-Sandwich problem
• An optimal generalization of the colorful Carathéodory theorem

This page was built for publication: Computational aspects of the colorful Carathéodory theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1991350)