@book{3d0aaeaf008d4f3d8f43c3ef8a5b1211,
title = "Fully-dynamic orthogonal range reporting on RAM",
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.",
keywords = "dynamic data structures, orthogonal range reporting, computational geometry, comparison model, complexity analysis",
author = "Mortensen, \{Christian Worm\}",
year = "2003",
month = apr,
language = "English",
series = "IT University Technical Report Series",
number = "TR-2003-22",
publisher = "IT-Universitetet i K{\o}benhavn",
address = "Denmark",
edition = "TR-2003-22",
}