Questions tagged [range-searching]
The range-searching tag has no usage guidance.
8
questions
1
vote
0answers
32 views
Practical worst-case polylogarithmic dynamic orthogonal range queries?
There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
4
votes
1answer
82 views
Complexity of Parallelogram Range Minimum Query
Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs?
More formally, answering the query
$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$...
3
votes
0answers
76 views
Triangular range counting query in poly-logarithmic time
What is the minimal space requirement for
triangular range counting queries in plane
if one wants to process each query in poly-logarithmic time?
In [Goswami et al, 2004]
they preprocess the ...
3
votes
1answer
150 views
Range searching: what is $\epsilon$?
I am interested in range searching purely as a black box in another problem. One problem in particular is that of shooting 2D rays among 2D segments. It seems that Agarwal and Matousek have a well ...
1
vote
1answer
120 views
What methods exist for returning all points within an arbitrary closed shape?
I have been reading about range search algorithms, but most that I read apply only to a simple range (such as a standard rectangle in 2d).
In a similar fashion, what options exist for range search ...
10
votes
4answers
840 views
Costs of performing approx. nearest neighbor search in a skip quadtree
NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$?
Quadtrees are efficient ...
5
votes
1answer
551 views
Dynamic Tree Marked Ancestor Queries
Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it ...
4
votes
1answer
735 views
Offline multidimensional RMQ/RSQ in query model
Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ)
you are given a $d$-dimensional array
with $n$ elements, and given a
$d$-dimensional box, you wish to
determine the max/...
