Geometric separability using orthogonal objects (Q2122791)

A bichromatic point is a point that is mixed with two base colors, like, e.g., red and blue. A separator is an object that separates these two colors. In this paper the geometric separability problem is studied for bichromatic point sets in the plane. Four cases are considered: when the separator is a) a rectangular annulus of fixed orientation, b) a rectangular annulus of arbitrary orientation, c) a square annulus of fixed orientation, and d) an orthogonal convex polygon. Additionally, respective algorithms of separation according to the above cases and working in polynomial time are given.