In * Proc. 38th International Colloquium on Automata, Languages, and Programming*, volume 6755 of * Lecture Notes in Computer Science*, pages 256-267. Springer Verlag, Berlin, 2011.

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*(log^{2} *n* +
*t*) worst case time, and *O*(log^{2} *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*(log^{3} *n*) to *O*(log^{2} *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.

© Springer-Verlag Berlin Heidelberg 2011. All rights reserved.

**Online version**

icalp11.pdf (335 Kb)

**DOI**

**BIBT _{E}X entry**

@incollection{icalp11, author = "Gerth St{\o}lting Brodal and Konstantinos Tsakalidis", booktitle = "Proc. 38th International Colloquium on Automata, Languages, and Programming", doi = "10.1007/978-3-642-22006-7_22", isbn = "978-3-642-22005-0", pages = "256-267", publisher = "Springer {V}erlag, Berlin", series = "Lecture Notes in Computer Science", title = "Dynamic Planar Range Maxima Queries", volume = "6755", year = "2011" }