  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.
