On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems

Knauer, Christian; Tiwary, Hans Raj; Werner, Daniel

doi:10.4230/LIPIcs.STACS.2011.649

Document

On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems

Authors Christian Knauer, Hans Raj Tiwary, Daniel Werner

Part of: Volume: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2011-03-11

PDF

File

PDF

LIPIcs.STACS.2011.649.pdf

Filesize: 0.64 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2011.649
URN: urn:nbn:de:0030-drops-30514

Subject Classification

Keywords

computational geometry
combinatorial geometry
ham-sandwich cuts
parameterized complexity.

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

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

Author Details

Christian Knauer

Hans Raj Tiwary

Daniel Werner

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail