Questions tagged [range-searching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10
votes
4answers
781 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
547 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
677 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/...
4
votes
1answer
75 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
1answer
149 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 ...
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 ...
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 ...