Finding Monochromatic L-Shapes in Bichromatic Point Sets
Farnaz Sheikhi, de Mt Mark Berg, Ali Mohades, Mansoor Davoodi · 2010
Given a set R of red points and a set B of blue points in the plane of total size n, we study the problem of determining all angles for which there exists an L-shape containing all points from B without containing any points from R. We propose an algorithm to solve the problem in O(n^2 log n) time and O(n) storage. We also describe an output-sensitive algorithm that reports all angles in O(n^{5/3+\\epsilon} + k log k) time and O(n^{5/3+\\epsilon}) storage, where k is the number of reported angular intervals.