petek, 7. oktober 2011 Seminar MARA

V ponedeljek, 10. oktobra 2011, bo ob 15.00  uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanje v okviru skupnega SEMINARJA ZA MATEMATIČNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP FAMNIT, Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP PINT, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.

RAČUNALNIŠKI SEMINAR - OBVEZNA UDELEŽBA PODIPLOMSKIH ŠTUDENTOV

Prostor: FAMNIT-1-RU1 (zgornja računalnica)  ob 15:00

Predavatelj: Gerth Stolting Brodal

Title: Dynamic Planar Range Maxima Queries.

Abstract:
We consider the dynamic two-dimensional maxima query problem. Let P be a set of n points in the plane. A point is maximal if it is not dominated by any other point in P. We describe two data structures that support the reporting of the t maximal points that dominate a given query point, and allow for insertions and deletions of points in P. In the pointer machine model we present a linear space data structure with O(log n + t) worst case query time and O(log n) worst case update time. This is the first dynamic data structure for the planar maxima dominance query problem that achieves these bounds in the worst case. The data structure also supports the more general query of reporting the maximal points among the points that lie in a given 3-sided orthogonal range unbounded from above in the same complexity. We can support 4-sided queries in O(log2 n + t) worst case time, and O(log2 n) worst case update time, using O(n*log n) space, where t is the size of the output. This improves the worst case deletion time of the dynamic rectangular visibility query problem from O(log3 n) to O(log2 n). We adapt the data structure to the RAM model with word size w, where the coordinates of the points are integers in the range U = {0,...,2^w-1}. We present a linear space data structure that supports 3-sided range maxima queries in O((log n)/(loglog n) + t) worst case time and updates in O((log n)/(loglog n)) worst case time. These are the first sublogarithmic worst case bounds for all operations in the RAM model.

Joint work with Konstas Tsakalidis

VABLJENI!