Separating bichromatic point sets by L-shapes

Given a set R of red points and a set B of blue points in the plane, we study the problem of determining all angles for which there exists an L-shape containing all points from B and no points from R  . We propose a worst-case optimal algorithm to solve this problem in O(n2)O(n2) time and O(n)O(n) storage, where n=|R|+|B|n=|R|+|B|. We also describe an output-sensitive algorithm that reports these angles in O(n8/5+ε+klog⁡k)O(n8/5+ε+klog⁡k) time and O(n8/5+ε)O(n8/5+ε) storage, where k   is the number of reported angular intervals and ε>0ε>0 is any fixed constant.