1
|
EPPSTEIN DAVID, GOODRICH MICHAELT, SUN JONATHANZ. SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS. ACTA ACUST UNITED AC 2011. [DOI: 10.1142/s0218195908002568] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022]
Abstract
We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R2) or the skip octree (for point data in Rd, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined “box”-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.
Collapse
Affiliation(s)
- DAVID EPPSTEIN
- Department of Computer Science, Donald Bren School of Information and Computer Sciences, University of California, Irvine, CA 92697-3435, USA
| | - MICHAEL T. GOODRICH
- Department of Computer Science, Donald Bren School of Information and Computer Sciences, University of California, Irvine, CA 92697-3435, USA
| | - JONATHAN Z. SUN
- School of Computing, University of Southern Mississippi, 118 College Drive #5106, Hattiesburge, MS 39406, USA
| |
Collapse
|