Name
Abstract | ||
|---|---|---|
We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let S be a set of n points in the plane, where each point p in S is assigned a weight w(p) that is polynomial in n, and define the rank of p to be r(p) = left perpendicularlog w(p)right perpendicular . Then the priority range tree can be used to report all points in a three- or four-sided query range R with rank at least left perpendicularlog wright perpendicular in time O(log W/w + k), and report k highest-rank points in R in time O(loglogn + log W/w' + k), where W = Sigma(p is an element of S) w(P), w' is the smallest weight of any point reported, and k is the output size. All times assume the standard RAM model of computation. If the query range of interest is three sided, then the priority range tree occupies O(n) space, otherwise O(n log n) space is used to answer four-sided queries. These queries are motivated by the Weber-Fechner Law, which states that humans perceive and interpret data on a logarithmic scale. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-17517-6_11 | ALGORITHMS AND COMPUTATION, PT I |
Keywords | DocType | Volume |
computational geometry,data structure,model of computation | Journal | 6506 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
16 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael T. Goodrich | 1 | 4351 | 331.47 |
| Darren Strash | 2 | 238 | 17.72 |