Rectangle Enclosure Reporting in Linear Space Revisited
George Lagogiannis, Christos H. Makris, Yannis Panagis, Spyros Sioutas, Kostas Tsichlas · Universitätsbibliothek Gießen · 2003
We present a new algorithm for reporting all the enclosures in a set of plane rectangles in $O(n\log n\log\log n + k\log \log n)$ time and linear space ($k$ denotes the output size). The result is already known (it has already been achieved by two previous papers), however the proposed algorithm follows a different approach.