Knauer, Christian ;
Tiwary, Hans Raj ;
Werner, Daniel
On the computational complexity of HamSandwich cuts, Helly sets, and related problems
Abstract
We study several canonical decision problems arising from some wellknown 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 NPhard) if the dimension is part of the input. This is done by fptreductions (which are actually ptimereductions) from the dSum 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 ExponentialTime Hypothesis (ETH) is false.
The technique of embedding dSum into a geometric setting is conceptually much simpler than direct fptreductions 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.
BibTeX  Entry
@InProceedings{knauer_et_al:LIPIcs:2011:3051,
author = {Christian Knauer and Hans Raj Tiwary and Daniel Werner},
title = {{On the computational complexity of HamSandwich cuts, Helly sets, and related problems}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {649660},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3051},
URN = {urn:nbn:de:0030drops30514},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.649},
annote = {Keywords: computational geometry, combinatorial geometry, hamsandwich cuts, parameterized complexity.}
}
2011
Keywords: 

computational geometry, combinatorial geometry, hamsandwich cuts, parameterized complexity. 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Related Scholarly Article: 


Issue date: 

2011 
Date of publication: 

2011 