[Mittagsseminar TI] Mittagsseminar 5.7.

[Alexander Kauer <alexander.kauer@fu-berlin.de>]

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
***************************************************