STOC Conference 2003 Conference Paper
Dynamic rectangular intersection with priorities
- Haim Kaplan
- Eyal Molad
- Robert Endre Tarjan
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.