论文标题
圆上点的红蓝点分离
Red-Blue Point Separation for Points on a Circle
论文作者
论文摘要
给定一组红点和平面中蓝点的B集b，红蓝点的分离问题询问大多数k线是否与b分开，也就是说，由溶液线诱导的每个单元格是空的，或者是单色的（仅包含一种颜色的点）。问题的一个常见变体是何时需要轴平行。已知该问题在两种情况下都是NP完整的，而W [1] hard在前一种环境中由K参数和后者的FPT参数化。当点位于圆上时，我们为特殊情况演示了多项式时间算法。此外，我们还证明了在轴平行设置中相关问题的W hard度，其中问题是是否有p水平和q垂直线与B分开。
Given a set R of red points and a set B of blue points in the plane, the Red-Blue point separation problem asks if there are at most k lines that separate R from B, that is, each cell induced by the lines of the solution is either empty or monochromatic (containing points of only one color). A common variant of the problem is when the lines are required to be axis-parallel. The problem is known to be NP-complete for both scenarios, and W[1]-hard parameterized by k in the former setting and FPT in the latter. We demonstrate a polynomial-time algorithm for the special case when the points lie on a circle. Further, we also demonstrate the W-hardness of a related problem in the axis-parallel setting, where the question is if there are p horizontal and q vertical lines that separate R from B. The hardness here is shown in the parameter p.
