3
$\begingroup$

The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly.

This was solved beautifully and optimally in a paper by Afshani and Chan. Their solution uses $O(n)$ preprocessing time and $O(\log n + k)$ time to answer a query, where $k$ is the number of points reported.

Consider the following variant. We have $n$ points in the plane but now we query with 2 points $p_1$ and $p_2$ and a radius $r$. A query should return the points that are within distance $r$ of both $p_1$ and $p_2$.

Clearly we could just run the algorithm of Afshani and Chan twice and return the intersection of the two given sets of points. However the intersection of the two sets may be much smaller than their union.

Is there a known data structure that takes $O(\log n + k')$ time per query where $k'$ is the number of points to be reported?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.