文章基本信息

标题：On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems
本地全文：下载
作者：Christian Knauer ; Hans Raj Tiwary ; Daniel Werner 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：649-660
DOI：10.4230/LIPIcs.STACS.2011.649
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：computational geometry; combinatorial geometry; ham-sandwich cuts; parameterized complexity.