Asymmetric Separation Problem for Bichromatic Point Set

Abstract

We study the Generalized Red-Blue Annulus Cover problem for two sets of points, red ($R$) and blue ($B$), where each point $p\in R\cup B$ is associated with a positive penalty $\mathcal{P}(p)$. The red points have non-covering penalties, and the blue points have covering penalties. The objective is to compute an annulus (either a rectangular or a circular) $\mathcal{A}$ such that the value of the function $\mathcal{P}(R^{out})+\mathcal{P}(B^{in})$ is minimum, where $R^{out}\subseteq R$ is the set of red points not covered by $\mathcal{A}$, and $B^{in}\subseteq B$ is the set of blue points covered by $\mathcal{A}$. We study the problem for various types of axis-parallel rectangular annulus and circular annulus in one and two dimensions. We also study a restricted version of the rectangular annulus cover problem, where the center of the annulus is constrained to lie on a given horizontal line $L$. We design a polynomial-time algorithm for each type of annulus.

35 pages, 13 figures