[Mittagsseminar TI] Mittagsseminar 5.7.
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 3.7.2018
Alexander Kauer
zum Thema: Dynamic Rectangular Intersection with Priorities
Zusammenfassung:
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(logn) time, deletions in O(lognloglogn) 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(logn) 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.
***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************
