Red-blue point separation for points on a circle

Show simple item record Misra, Neeldhara Mittal, Harshil Sethia, Aditi 2020-05-27T14:12:54Z 2020-05-27T14:12:54Z 2020-05
dc.identifier.citation Misra, Neeldhara; Mittal, Harshil and Sethia, Aditi, "Red-blue point separation for points on a circle", arXiv, Cornell University Library, DOI: arXiv:2005.06046, May 2020. en_US
dc.description.abstract 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.
dc.description.statementofresponsibility by Neeldhara Misra, Harshil Mittal and Aditi Sethia
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title Red-blue point separation for points on a circle en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account