Dynamic Planar Range Maxima Queries

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

Standard

Dynamic Planar Range Maxima Queries. / Brodal, Gerth Stølting; Tsakalidis, Konstantinos.

In: Lecture Notes in Computer Science, Vol. 6755 , 2011, p. 256-267.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

Harvard

Brodal, GS & Tsakalidis, K 2011, 'Dynamic Planar Range Maxima Queries' Lecture Notes in Computer Science, vol. 6755 , pp. 256-267. https://doi.org/10.1007/978-3-642-22006-7_22

APA

Brodal, G. S., & Tsakalidis, K. (2011). Dynamic Planar Range Maxima Queries. Lecture Notes in Computer Science, 6755 , 256-267. https://doi.org/10.1007/978-3-642-22006-7_22

CBE

Brodal GS, Tsakalidis K. 2011. Dynamic Planar Range Maxima Queries. Lecture Notes in Computer Science. 6755 :256-267. https://doi.org/10.1007/978-3-642-22006-7_22

MLA

Brodal, Gerth Stølting and Konstantinos Tsakalidis. "Dynamic Planar Range Maxima Queries". Lecture Notes in Computer Science. 2011, 6755 . 256-267. https://doi.org/10.1007/978-3-642-22006-7_22

Vancouver

Brodal GS, Tsakalidis K. Dynamic Planar Range Maxima Queries. Lecture Notes in Computer Science. 2011;6755 :256-267. https://doi.org/10.1007/978-3-642-22006-7_22

Author

Brodal, Gerth Stølting ; Tsakalidis, Konstantinos. / Dynamic Planar Range Maxima Queries. In: Lecture Notes in Computer Science. 2011 ; Vol. 6755 . pp. 256-267.

Bibtex

@inproceedings{234ac94b03794c3d8187a836ba97e49d,
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(logn + t) worst case query time and O(logn) 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(nlogn) 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(logn/loglogn+t) worst case time and updates in O(logn/loglogn) worst case time. These are the first sublogarithmic worst case bounds for all operations in the RAM model.",
author = "Brodal, {Gerth St{\o}lting} and Konstantinos Tsakalidis",
year = "2011",
doi = "10.1007/978-3-642-22006-7_22",
language = "English",
volume = "6755",
pages = "256--267",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

RIS

TY - GEN

T1 - Dynamic Planar Range Maxima Queries

AU - Brodal, Gerth Stølting

AU - Tsakalidis, Konstantinos

PY - 2011

Y1 - 2011

N2 - 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(logn + t) worst case query time and O(logn) 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(nlogn) 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(logn/loglogn+t) worst case time and updates in O(logn/loglogn) worst case time. These are the first sublogarithmic worst case bounds for all operations in the RAM model.

AB - 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(logn + t) worst case query time and O(logn) 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(nlogn) 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(logn/loglogn+t) worst case time and updates in O(logn/loglogn) worst case time. These are the first sublogarithmic worst case bounds for all operations in the RAM model.

U2 - 10.1007/978-3-642-22006-7_22

DO - 10.1007/978-3-642-22006-7_22

M3 - Conference article

VL - 6755

SP - 256

EP - 267

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -