Dynamic rectangular intersection with priorities

We present efficient data structures to maintain dynamic set of rectangles, each with priority assigned to it, such that we can efficiently find the rectangle of maximum priority containing a query point. Our data structures support insertions and deletions of rectangles. In one dimension, when rectangles are intervals, our most efficient data structure supports queries and insertions in O(log n) time, deletions in O(log n log log n) time and requires linear space. When intervals are guaranteed to be nonoverlapping (but one can be nested within the other) we obtain a simpler data structure that supports all operations in O(log n) time.

Authors

• Haim Kaplan
• Eyal Molad
• Robert Endre Tarjan

Keywords

• orthogonal range searching
• packet classification
• rectangular intersection
• rectangular point location