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 algorithms across arbitrary closed shapes? For example, if I had a binary image of a person, and random points across the image, how do I determine which points lie on the portion of the person?

  • $\begingroup$ Have you tried Google? $\endgroup$ – Janoma Oct 13 '11 at 1:46
  • 1
    $\begingroup$ It's not clear to me if you really want range search in your application. $\endgroup$ – Yoshio Okamoto Oct 13 '11 at 13:37

There are no options.

For any set of $n$ points, if you want to answer range queries for arbitrary ranges, all $2^n$ subsets are possible answers. (In fact, for any set of $n$ points in convex position, every subset is the intersection with some convex range.) It follows immediately that any query algorithm (describable as a decision tree) requires $\Omega(n)$ time, no matter how much time and space you spend preprocessing the points.

Equivalently: The range space (points in the plane, convex regions in the plane) has unbounded VC-dimension, so there's no hope for an efficient range searching algorithm.


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.