28:
query asks for a list of the points that match the query. The query is often specified by a geometric shape, containing all the points that should match, and is called a range. Range reporting is a special case of
127:
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
71:
to find the point closest to the start of a query interval, and then scan the array from that point forwards to list all of the points in the interval. Storing this data structure uses
40:
from a collection of points that can answer queries efficiently. Because the worst case output size for a range reporting query, measured as a function of the data set size
145:
67:, range reporting queries can be handled by storing the data in a sorted array. With this structure, one can use
49:
150:
64:
17:
130:, Contemporary Mathematics, vol. 223, American Mathematical Society Press, pp. 1–56
33:, in which queries may return other kinds of aggregate information about points in a range.
8:
111:
107:
122:
118:
48:
itself, much of the research on range reporting data structures has investigated
37:
139:
68:
63:
For example, for one-dimensional (numeric) data with query ranges that are
30:
21:
36:
Range reporting queries are often handled by building a
52:, where the query time is analyzed in terms of both
56:and the number of reported points (often denoted
137:
106:
82:(linear) space, and it handles queries in time
112:"Geometric Range Searching and Its Relatives"
138:
13:
14:
162:
1:
100:
7:
125:; Pollack, Richard (eds.),
50:output-sensitive algorithms
10:
167:
146:Geometric data structures
110:; Erickson, J. (1999),
18:computational geometry
119:Chazelle, Bernard
158:
131:
116:
96:
81:
59:
55:
47:
43:
166:
165:
161:
160:
159:
157:
156:
155:
151:Database theory
136:
135:
114:
103:
83:
72:
57:
53:
45:
41:
31:range searching
26:range reporting
12:
11:
5:
164:
154:
153:
148:
134:
133:
123:Goodman, Jacob
108:Agarwal, P. K.
102:
99:
38:data structure
9:
6:
4:
3:
2:
163:
152:
149:
147:
144:
143:
141:
129:
124:
120:
113:
109:
105:
104:
98:
94:
90:
86:
79:
75:
70:
69:binary search
66:
61:
51:
39:
34:
32:
27:
23:
19:
126:
92:
88:
84:
77:
73:
62:
35:
25:
15:
97:per query.
140:Categories
101:References
24:theory, a
65:intervals
44:, can be
22:database
128:College
117:, in
115:(PDF)
87:(log
20:and
60:).
16:In
142::
121:;
91:+
132:.
95:)
93:k
89:n
85:O
80:)
78:n
76:(
74:O
58:k
54:n
46:n
42:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.