Separability by two lines and by nearly straight polygonal chains (Q1885815)

The authors consider separability problems between two sets of points in the plane, a ``red'' set \(R\) and a ``blue'' set \(B\), with the total number of points being \(N\). The objective is to separate \(R\) and \(B\) by a polygonal object that is as ``simple'' as possible. This problem does have some practical relevance when trying to simplify a given set of ``negative'' and ``positive'' sample points, which is a frequent problem in pattern recognition or in geographic information systems. The main results are two \(O(N\log N)\) algorithms, one for deciding double-wedge separability, the other for deciding constant-turn separability of a point set.