Affordable Access

Publisher Website

Space efficient data structures for dynamic orthogonal range counting

Authors
Journal
Computational Geometry
0925-7721
Publisher
Elsevier
Volume
47
Issue
2
Identifiers
DOI: 10.1016/j.comgeo.2013.08.007
Keywords
  • Succinct Data Structure
  • Geometric Data Structure
  • Dynamic Data Structure
  • Orthogonal Range Counting
  • Dynamic Orthogonal Range Counting
Disciplines
  • Design

Abstract

Abstract We present a linear-space data structure that maintains a dynamic set of n points with coordinates of real numbers in the plane to support orthogonal range counting in O((lgnlglgn)2) worst-case time, and insertions and deletions in O((lgnlglgn)2) amortized time. This provides faster support for updates than previous results with the same bounds on space cost and query time. We also consider the same problem for points on a U×U grid, and design the first succinct data structure for a dynamic integer sequence, S, to support range counting queries defined as follows: Given a range, [i1..i2], of indices and a range, [v1..v2], of values, count the number of entries of S[i1..i2] that store integers from [v1..v2].

There are no comments yet on this publication. Be the first to share your thoughts.