In a natural variant of the comparison model, we show that there exists aconstant ω<1 such that the fully-dynamic d -dimensional orthogonal range reporting problem for d≥2 can be solved in time O(logω+d−2n) for updates and time O((logn/loglogn)d−1+r) for queries. Here n is the number of points stored and r is the number of points reported. The space usage is O(nlogω+d−2n). In the standard comparison model the result holds for d≥3.
Udgivelsessted | Copenhagen |
---|
Forlag | IT-Universitetet i København |
---|
Udgave | TR-2003-22 |
---|
Antal sider | 33 |
---|
ISBN (Elektronisk) | 87-7949-030-1 |
---|
Status | Udgivet - apr. 2003 |
---|
Udgivet eksternt | Ja |
---|
Navn | IT University Technical Report Series |
---|
Nummer | TR-2003-22 |
---|
ISSN | 1600-6100 |
---|