The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension
The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension
复制标题
一些无界维几何问题的参数化复杂性
DOI：
10.1007/978-3-642-11269-0_16
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
G. Rote
中科院分区：
文献类型：
--
作者：
P. Giannopoulos;Christian Knauer;G. Rote
我们研究以下关于维度 d 的基本几何问题的参数化复杂性：
i) 给定 n 点？ d ，计算它们的最小封闭圆柱体。
ii) 给定两个 n 点集 ? d ，决定它们是否可以被两个超平面分开。
iii) 给定一个包含 d 个变量的 n 个线性不等式的系统，找到一个最大尺寸的可行子系统。
我们表明，当通过维度 d 进行参数化时，所有这些问题（的决策版本）都是 W[1]-困难的。我们的约简还给出了 n ?(d) 时间下限（根据指数时间假设）。
We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension d:
i) Given n points in ? d , compute their minimum enclosing cylinder.
ii) Given two n-point sets in ? d , decide whether they can be separated by two hyperplanes.
iii) Given a system of n linear inequalities with d variables, find a maximum size feasible subsystem.
We show that (the decision versions of) all these problems are W[1]-hard when parameterized by the dimension d. Our reductions also give a n ?(d)-time lower bound (under the Exponential Time Hypothesis).