Algorithm for the Removal of Rectangle Containment for Rectangle Spline Generation

ABSTRACT

Given a set of axis-aligned rectangles in the plane, this paper presents an algorithm for the removal of rectangle containment as well as rectangle enclosures. That is, given a query rectangle R_q, this algorithm removes all rectangles R_k, … , R_l from the rectangle set that are contained in R_q. It also removes R_q if there is a rectangle R_j that encloses R_q. The algorithm, initially implemented for rectangle spline generation using rectangles as building blocks, is fast, easy to implement and maintain, it can be run on parallel machines such as GPUs at no extra cost, but it requires extra memory to store the rectangle indexes for quick access and space partitioning.

GRAPHICAL ABSTRACT

Keywords:

• rectangle containment
• rectangle splines
• spatial data structures
• GPUs

ACKNOWLEDGEMENTS

This work was supported in part by Synopsys, Inc. and Najran University. All opinions, findings and conclusions are those of the authors and do not necessarily reflect the funding agencies or the institutions the authors are affiliated with.