Separating bichromatic point sets by L-shapes (Q904108)

The paper deals with the following problem: Given a blue point set \(B\) and a red point set \(R\), find all angles \(\theta\) for which there exists an L-shape \(L\) with orientation \(\theta\) such that \(B \subset L\) and \(R \cap L = \emptyset\). The L-shape is defined as a set-theoretic difference \(M \backslash M'\) of two axis-aligned rectangles \(M\) and \(M'\) such that the top-right corners of \(M\) and \(M'\) coincide. To solve the problem, the authors present two algorithms. In both cases they use rotational sweep, i.e., they increase \(\theta\) from \(0\) to \(2 \pi\) and report the angular intervals for which there is a blue L-shape (L-shape containing the blue point set) while sweeping. The first algorithm is based on the idea to pre-compute all non-crossing events and then to compute all the crossing events occurring between two consecutive non-crossing events. The authors firstly describe an algorithm that achieves \(O(n^2)\) time complexity and uses \(O(n \alpha(n))\) storage, where \(n = |R| + |B|\) and \(\alpha\) is the extremely slow-growing inverse of the Ackermann function. Then, they refine the algorithm so that it uses only linear storage. Moreover, they show that the proposed algorithm is a worst-case optimal algorithm. The second proposed algorithm is an output-sensitive algorithm. This algorithm outperforms the first algorithm in terms of time complexity when the output size is subquadratic. It is based on the idea that the number of non-crossing events is small, and the number of crossing events is proportional to the output size. The authors show that the proposed algorithm obtains \(O(n^{8/5 + \varepsilon} + k \log k)\) time and uses \(O(n^{8/5 + \varepsilon})\) storage, where \(k\) is the number of reported angular intervals and \(\varepsilon > 0\) is any fixed constant.