LIPIcs.STACS.2011.649.pdf
- Filesize: 0.64 MB
- 12 pages
Document
On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems
Authors
-
Part of:
Volume:
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-03-11
Cite As Get BibTex
Christian Knauer, Hans Raj Tiwary, and Daniel Werner. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 649-660, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.STACS.2011.649
Abstract
We study several canonical decision problems arising from some well-known theorems from combinatorial geometry. Among others, we show that computing the minimum size of a Caratheodory set and a Helly set and certain decision versions of the hs cut problem are W[1]-hard (and NP-hard) if the dimension is part of the input. This is done by fpt-reductions (which are actually ptime-reductions) from the d-Sum problem. Our reductions also imply that the problems we consider cannot be solved in time n^{o(d)} (where n is the size of the input), unless the Exponential-Time Hypothesis (ETH) is false.
The technique of embedding d-Sum into a geometric setting is conceptually much simpler than direct fpt-reductions from purely combinatorial W[1]-hard problems (like the clique problem) and has great potential to show (parameterized) hardness and (conditional) lower bounds for many other problems.
Subject Classification
Keywords
- computational geometry
- combinatorial geometry
- ham-sandwich cuts
- parameterized complexity.
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads