Fully-dynamic orthogonal range reporting on RAM

Christian Worm Mortensen

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

Abstract

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.
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2003-22
Antal sider33
ISBN (Elektronisk)87-7949-030-1
StatusUdgivet - apr. 2003
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2003-22
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Fully-dynamic orthogonal range reporting on RAM'. Sammen danner de et unikt fingeraftryk.

Citationsformater