A Rectangle-Intersection Algorithm with Limited Resource Requirements

It is demonstrated that power-efficient software also requires simplicity and the use of elementary data structures in addition to asymptotically optimal CPU and memory requirements. Though in the past few decades much effort has been devoted to reporting all k intersecting pairs in a planar set of n iso-oriented rectangles, all the known algorithms using elementary data structures, such as linked lists, are either not optimal, report some intersections repeatedly or fail to report some altogether. A simpler algorithm is proposed that uses only linear arrays and that takes O(n log n + k) time and O(n) space, which are the best possible under the algebraic RAM model of computation. The algorithm is designed for systems with limited resources, such as mobile 3D graphics, and can be implemented in less than 100 lines of Java code.