Questions tagged [range-searching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 views

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
44 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 ...
templatetypedef's user avatar
4 votes
1 answer
106 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]$...
user3508551's user avatar
  • 1,143
3 votes
0 answers
93 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 ...
Sayan Bandyapadhyay's user avatar
3 votes
1 answer
164 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 ...
John's user avatar
  • 235
1 vote
1 answer
124 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 ...
cup's user avatar
  • 11
10 votes
4 answers
1k 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 ...
0__'s user avatar
  • 173
5 votes
1 answer
590 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 ...
0__'s user avatar
  • 173
4 votes
1 answer
935 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/...
Grigory Yaroslavtsev's user avatar