0
$\begingroup$

Suppose that there are a set of $n$ points $P = \{(x_1,y_1), \dots, (x_n,y_n)\}$ in 2D.

Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ running time that can find the point set $Q \subseteq P$ containing those points of $P$ that are inside the circle with center $(a,b)$ and radius $r$?

(That is, I want to find all points in $P$ with coordinates $(i,j)$ such that $(i-a)^2 + (j-b)^2 \leq r^2$.)

[I originally asked about a solution with running time $O(\log n)$, but as Pål GD correctly points out, the answer to that question was "not possible".]

$\endgroup$
  • 2
    $\begingroup$ But the answer to the revised question is still "Obviously, no." You still have to look at all the points to see which ones are in the solution set and the solution set could very well be empty. $\endgroup$ – David Richerby Mar 8 '15 at 16:56
  • $\begingroup$ Do you have the luxury to first index $P$ in an offline stage? $\endgroup$ – Tolga Birdal Apr 28 '16 at 20:46
3
$\begingroup$

You are asking for a sublinear time algorithm which for some inputs must output every element. So the answer is, as David Richerby argues, no.

A better question is probably an output-sensitive version of the problem: Can you solve it in $O(\log n + |S|)$ where $S$ is the solution. That is, logarithmic in the input, and linear in the output.

$\endgroup$
  • 1
    $\begingroup$ But it's obviously not possible in time $O(\log n + |S|)$, since the answer could be $S=\emptyset$, which you'd have to compute in time $O(\log n)$, which can't be done. Also, your answer appears to be just an endorsement of my answer, plus a suggestion of how to improve the question. That should be an upvote and a comment, not an answer. $\endgroup$ – David Richerby Mar 8 '15 at 17:01
  • $\begingroup$ What if the input is sorted? My point of adding the extra dependence on output was that in sublinear algorithms we almost always have extra properties. Take binary search, for instance. Your answer was 'no obviously not'. I don't think that was a good answer, that's all. Hence no upvote from me. $\endgroup$ – Pål GD Mar 8 '15 at 21:40
3
$\begingroup$

Obviously not. You must inspect all the points and, on a classical, deterministic computer, you can't possibly look at $n$ points in only $O(\log n)$ time.

Note that this answer applies equally to the original question (is it possible in $\log n$ time?) and the revised one (is it possible in $|Q|+\log n$ time?). The answer could well be $Q=\emptyset$, but you can't figure that out in time $o(n)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.