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".]

Improve this question
$\endgroup$
2
  • 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, 2015 at 16:56
  • $\begingroup$ Do you have the luxury to first index $P$ in an offline stage? $\endgroup$
    – Tolga Birdal
    Apr 28, 2016 at 20:46

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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, 2015 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, 2015 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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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