Amortized Bounds for Dynamic Orthogonal Range Reporting

摘要: We consider the fundamental problem of 2-D dynamic orthogonal range reporting for 2- and 3-sided queries in standard word RAM model. While many previous data structures use O(logn /loglogn) update time, we achieve faster O(log1/2 + e n) O(log2/3 times queries, respectively. Our have optimal / loglogn) query time. Only Mortensen [14] had previously lowered time convincingly below O(logn), with 3- 4-sided supporting updates O(log5/6 O(log7/8 In practice, fast are often as important so make a step forward an that has not seen any progress recent years. also obtain new results special case insertion-only emptiness, showing difference complexity between fully partially can be significant (i.e., Ω(polylog factor differences). particular, O((logn loglogn)2/3) loglogn)1/3) At other end our update/query trade-off curve, O(logn/loglogn) O(loglogn) contrast, pointer machine model, there only differences complexities reporting.