Dynamic rectangular intersection with priorities

Haim Kaplan, Eyal Molad, Robert E. Tarjan

Research output: Contribution to journalConference articlepeer-review

32 Scopus citations

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 languageEnglish (US)
Pages (from-to)639-648
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Orthogonal range searching
  • Packet classification
  • Rectangular intersection
  • Rectangular point location

Fingerprint

Dive into the research topics of 'Dynamic rectangular intersection with priorities'. Together they form a unique fingerprint.

Cite this