Computational Aspects of the Colorful Carathéodory Theorem

Authors Wolfgang Mulzer, Yannik Stein



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.44.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Wolfgang Mulzer
Yannik Stein

Cite AsGet BibTex

Wolfgang Mulzer and Yannik Stein. Computational Aspects of the Colorful Carathéodory Theorem. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 44-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.44

Abstract

Let P_1,...,P_{d+1} be d-dimensional point sets such that the convex hull of each P_i contains the origin. We call the sets P_i color classes, and we think of the points in P_i as having color i. A colorful choice is a set with at most one point of each color. The colorful Caratheodory theorem guarantees the existence of a colorful choice whose convex hull contains the origin. So far, the computational complexity of finding such a colorful choice is unknown. We approach this problem from two directions. First, we consider approximation algorithms: an m-colorful choice is a set that contains at most m points from each color class. We show that for any fixed epsilon > 0, an (epsilon d)-colorful choice containing the origin in its convex hull can be found in polynomial time. This notion of approximation has not been studied before, and it is motivated through the applications of the colorful Caratheodory theorem in the literature. In the second part, we present a natural generalization of the colorful Caratheodory problem: in the Nearest Colorful Polytope problem (NCP), we are given d-dimensional point sets P_1,...,P_n 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 local optima for the NCP problem is PLS-complete, while computing a global optimum is NP-hard.
Keywords
  • colorful Carathéodory theorem
  • high-dimensional approximation
  • PLS

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Emile Aarts and Jan Karel Lenstra, editors. Local search in combinatorial optimization. Princeton University Press, 2003. Google Scholar
  2. Jorge L. Arocha, Imre Bárány, Javier Bracho, Ruy Fabila, and Luis Montejano. Very colorful theorems. Discrete Comput. Geom., 42(2):142-154, 2009. Google Scholar
  3. Imre Bárány. A generalization of Carathéodory’s theorem. Discrete Math., 40(2-3):141-152, 1982. Google Scholar
  4. Imre Bárány and Shmuel Onn. Colourful linear programming and its relatives. Math. Oper. Res., 22(3):550-567, 1997. Google Scholar
  5. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. System Sci., 37(1):79-100, 1988. Google Scholar
  6. Jiří Matoušek. Lectures on discrete geometry. Springer, 2002. Google Scholar
  7. Frédéric Meunier and Antoine Deza. A further generalization of the colourful Carathéodory theorem. In Discrete geometry and optimization, volume 69 of Fields Inst. Commun., pages 179-190. Springer, New York, 2013. Google Scholar
  8. Frédéric Meunier and Pauline Sarrabezolles. Colorful linear programming, Nash equilibrium, and pivots. arxiv:1409.3436, 2014. Google Scholar
  9. Wil Michiels, Emile Aarts, and Jan Korst. Theoretical aspects of local search. Monographs in Theoretical Computer Science. Springer, Berlin, 2007. Google Scholar
  10. Gary L. Miller and Donald R. Sheehy. Approximate centerpoints with proofs. Comput. Geom., 43(8):647-654, 2010. Google Scholar
  11. Wolfgang Mulzer and Daniel Werner. Approximating Tverberg points in linear time for any fixed dimension. Discrete Comput. Geom., 50(2):520-535, 2013. Google Scholar
  12. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci., 48(3):498-532, 1994. Google Scholar
  13. Karanbir S. Sarkaria. Tverberg’s theorem via number fields. Israel J. Math., 79(2-3):317-320, 1992. Google Scholar
  14. Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput., 20(1):56-87, 1991. Google Scholar
  15. Helge Tverberg. Further generalization of Radon’s theorem. J. London Math. Soc., 43:352-354, 1968. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail