Maximum Separability by L-shapes
Farnaz Sheikhi, Ali Mohades · 2020
Let B be a set of blue points and R be a set of red points with total size n in the plane. In this paper, we propose a worst-case optimal O(n3) time algorithm to compute all axis- aligned L-shapes that contain maximum number of blue points without containing any red points. We also study this problem for arbitrarily oriented L-shapes, and present an O(n4α(n)) time algorithm to find these general L-shapes, where α(n) is the inverse of the Ackermann function.