David Eppstein - Publications

Publications with Jonathan Zheng Sun

• The skip quadtree: a simple dynamic data structure for multidimensional data.
  D. Eppstein, M. T. Goodrich, and J. Z. Sun.
  21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296–305.
  arXiv:cs.CG/0507049.
  Int. J. Comp. Geom. & Appl. 18(1-2): 131–160, 2008.

  We describe a data structure consisting of a sequence of compressed quadtrees for successively sparser samples of an input point set, with connections between the same squares in successive members of the sequence. Using this structure, we can insert or delete points and answer approximate range queries and approximate nearest neighbor queries in O(log n) time per operation.

  (SoCG05 talk slides)