...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >On the Parameterized Complexity of Red-Blue Points Separation
【24h】

On the Parameterized Complexity of Red-Blue Points Separation

机译：红蓝点分离的参数化复杂度

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the following geometric separation problem: Given a set R of red points and a set B of blue points in the plane, find a minimum-size set of lines that separate R from B. We show that, in its full generality, parameterized by the number of lines k in the solution, the problem is unlikely to be solvable significantly faster than the brute-force n^{O(k)}-time algorithm, where n is the total number of points. Indeed, we show that an algorithm running in time f(k)n^{o(k/log k)}, for any computable function f, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of k). Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result. Separating R from B with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time O^*(9^{|B|}) (assuming that B is the smallest set).
机译：我们研究以下几何分离问题：给定平面中的一组红点R和一组蓝点B，找到将R与B分开的最小尺寸的线组。通过解决方案中的行数k，该问题不可能比蛮力n ^ {O（k）}-时间算法（n是点的总数）快得多地解决。确实，我们证明了对于任何可计算函数f，在时间f（k）n ^ {o（k / log k）}中运行的算法都会反驳ETH。我们的简化至关重要地依赖于从具有大量不同斜率的集合中选择线（即，该数字不是k的函数）。假设要求线平行于轴线的问题变体的线数为FPT，我们得出以下初步结果。用最小尺寸的一组平行轴将R与B分开是任意一组的FPT，并且可以在时间O ^ *（9 ^ {| B |}）中求解（假定B是最小的集合） ）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号