Abstract
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. We can generalize these data structures to maintain rectangles with priorities in higher dimension using standard techniques based on segment trees. The space increases by a logarithmic factor per dimension, and we get a logarithmic slowdown for each operation per dimension. For nonoverlapping rectangles, we present a better data structure where we avoid the extra logarithmic factor on the query time. The general rectangular intersection problem with priorities and its special case of nonoverlapping rectangles both arise in packet classification by IP routers.
Original language | English (US) |
---|---|
Pages (from-to) | 639-648 |
Number of pages | 10 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 2003 |
Event | 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003 |
All Science Journal Classification (ASJC) codes
- Software
Keywords
- Orthogonal range searching
- Packet classification
- Rectangular intersection
- Rectangular point location