A new approach to rectangle intersections part I

Abstract

Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.

Keywords:

• Computational geometry
• rectilinearly-oriented rectangle
• intersection
• searching problem
• data structure
• concrete complexity

Categories and Subject Descriptors::

• E.1. [Data]: Data structures—trees
• F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical algorithms and problems—geometrical problems and computation, sorting and searching
• H.3.3 [Information Storage and Retrieval]: Information search and retrieval—search process