Questions tagged [range-searching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer

Complexity and Applications of performing $N$ divisions with "similar" results?

What is the complexity of performing $N$ divisions with "close" results and does it have applications in practice? It seems that some algorithms to divide a number $x$ by a number $y$ boil ...
J..y B..y's user avatar
  • 2,766
1 vote
0 answers

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 ...
templatetypedef's user avatar
4 votes
1 answer

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]$...
user3508551's user avatar
  • 1,143
3 votes
0 answers

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 ...
Sayan Bandyapadhyay's user avatar
3 votes
1 answer

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 ...
John's user avatar
  • 235
1 vote
1 answer

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 ...
cup's user avatar
  • 11
10 votes
4 answers

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 ...
0__'s user avatar
  • 173
5 votes
1 answer

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 ...
0__'s user avatar
  • 173
4 votes
1 answer

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/...
Grigory Yaroslavtsev's user avatar