Index
above, 315, 318
acceptable, 205
affine combination, 348
affine subspace, 348
algorithm
algCoverDisksGreedy, 170, 171
algDCover, 7–10
algDCoverSlow, 5–8, 10
algGrow,7,8,10
algLocalSearchKMed, 52, 56
algPntLoc_Qorder,23
algSlow, 308, 309
algWSPD, 31–33, 37, 38, 44
Child,14
compBasis, 211
compTarget, 211
DFS, 20, 31
GreedyKCenter, 49–51, 57
predecessor,23
QTFastPLI,14
QTGetNode,14
solveLPType, 211, 212
anchor, 54
ANN, see also approximate nearest neighbor
approximate near neighbor, 269
approximate nearest neighbor, 158, 158, 159–161,
233–256, 269, 274–276, 296, 306
k-nearest neighbor, 242
approximate Voronoi diagram, 254–256, 362
arrangement, 121
aspect ratio, 164
AVD, see also approximate Voronoi diagram
ball, 50, 243
approximation, 251
crossing metric, 90
open, 323
volume, 261
balls
set of balls
approximation, 251
union
radius r, 243
basic operations, 210
basis, 204
below, 315, 318
BFS, 334
BHST, 155, 156, 247, 249, 252
bi-Lipschitz, 265
binary space partition
rectilinear, 180
binomial
estimates, 82
black-box access, 47
blames, 172
bottom k-level, 193
Bourgain’s theorem
bounded spread, 329
low quality, 331
brick set, 257
bridge
t-bridge, 192
canonical, 195
feasible, 195
feasible, 193
canonical, 143, 195
bridge, 195
cut, 195
disks, 152
grid, 14
square, 14
Carathéodory’s theorem, 218
cell, 1, 253
query, 27, 237
center, 279
Chebychev’s inequality, 335
checkpoints, 178
Chernoff’s inequality, 340
simplified form, 340
closed, 347
closest pair, 36
closest point, 233
cluster, 325
clustering, 47
k-center, 49, 310
price, 49
problem, 49
357
Previous Page Next Page