Jump to content

User:Pzoxicuvybtnrm/Sandbox 4

From Wikipedia, the free encyclopedia
Simplex range searching.

In data structures, the range searching problem most generally consists of preprocessing a set S of objects, in order to determine which objects from S intersect with a query object, called a range. For example, if S is a set of points corresponding to the coordinates of several cities, a geometric variant of the problem is to find cities within a certain latitude and longitude range.

The range searching problem and the data structures that solve it are a fundamental topic of computational geometry. Applications of the problem arise in areas including geographical information systems (GIS) and computer-aided design (CAD), and databases.

Variations

[edit]

There are several variations of the problem, and different data structures may be necessary for different variations.[1] In order to obtain an efficient solution, several aspects of the problem need to be specified:

Data structures

[edit]

Orthogonal range searching

[edit]

In orthogonal range searching, the set S consists of points in dimensions, and the query consists of intervals in each of those dimensions. Thus, the query consists of a multi-dimensional axis-aligned rectangle. With an output size of , Jon Bentley used a k-d tree to achieve space and query time.[2] Bentley also proposed using range trees, which improved query time to but increased space to .[3] Dan Willard used downpointers, a special case of fractional cascading to reduce the query time further to . [4]

Further improvements have been made in the word RAM model of computation. Bernard Chazelle used compress range trees to achieve query time and space for range counting.[5] Joseph JaJa and others later improved this query time to for range counting, which matches a lower bound and is thus asymptotically optimal.[6]

As of 2015, the best results for range reporting found by Timothy M. Chan, Kasper Larsen, and Mihai Pătrașcu, also using compressed range trees in the word RAM model of computation, are one of the following:[7]

  • space, query time
  • space, query time
  • space, query time

In the orthogonal case, if one of the bounds is infinity, the query is called three-sided. If two of the bounds are infinity, the query is two-sided, and if none of the bounds are infinity, then the query is four-sided.

Dynamic range searching

[edit]

While in static range searching the set S is known in advance, dynamic range searching, insertions and deletions of points are allowed. In the incremental version of the problem, only insertions are allowed, whereas the decremental version only allows deletions. Kurt Mehlhorn and Stefan Näher created a data structure for dynamic range searching which uses dynamic fractional cascading to achieve space and query time.[8] Both incremental and decremental versions of the problem can be solved with query time, but it is unknown whether general dynamic range searching can be done with that query time.

Colored range searching

[edit]

The problem of colored range counting considers the case where points have categorical attributes. If the categories are considered as colors of points in geometric space, then a query is for how many colors appear in a particular range. Prosenjit Gupta and others described a data structure in 1995 which solved 2D orthogonal colored range counting in space and query time.[9]

Applications

[edit]

In addition to being considered in computational geometry, range searching, and orthogonal range searching in particular, has applications for range queries in databases. For example, colored range searching is used for and motivated by searching through categorical data.

References

[edit]
  1. ^ Agarwal, P. K.; Erickson, J. (1999), "Geometric Range Searching and Its Relatives" (PDF), in Chazelle, Bernard; Goodman, Jacob; Pollack, Richard (eds.), Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke College, Contemporary Mathematics, vol. 223, American Mathematical Society Press, pp. 1–56
  2. ^ Bentley, Jon (1975). "Multidimensional binary search trees used for associative searching". Communications of the ACM. 18 (9): 509–517.
  3. ^ Bentley, Jon (1980). "Multidimensional divide-and-conquer". Communications of the ACM. 23 (4): 214–229.
  4. ^ Willard, Dan (1985). "New data structures for orthogonal range queries". SIAM Journal of Computing. 14 (1): 232–253.
  5. ^ Chazelle, Bernard (1988). "A functional approach to data structures and its use in multidimensional searching". SIAM Journal on Computing. 17 (3): 427–462.
  6. ^ JaJa, Joseph; Mortensen, Christian; Shi, Qingmin (2005). "Space-efficient and fast algorithms for multidimensional dominance reporting and counting". International Symposium on Algorithms and Computation: 558–568.
  7. ^ Chan, Timothy; Larsen, Kasper; Pătrașcu, Mihai (2011). "Orthogonal range searching on the RAM, revisited". Symposium on Computational Geometry: 1–10.
  8. ^ Mehlhorn, Kurt; Näher, Stefan (1990). "Dynamic fractional cascading". Algorithmica. 5 (2): 215–241.
  9. ^ Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1995). "Further results on generalized intersection searching problems: Counting, reporting, and dynamization". Journal of Algorithms. 19 (2): 282–317.

Further reading

[edit]