<p>There are no options.</p>

<p>For any set of $n$ points, if you want to answer range queries for <em>arbitrary</em> 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 <em>convex</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-13T11:49:07.163Z
2011-10-13T11:49:07.163Z
Jeffε
<p>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).</p>

<p>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?</p>

CC BY-SA 3.0
2011-10-13T01:46:28.820Z
Have you tried Google?
Janoma
CC BY-SA 3.0
2011-10-13T13:37:50.220Z
It's not clear to me if you really want range search in your application.
Yoshio Okamoto
<cg.comp-geom><range-searching>
What methods exist for returning all points within an arbitrary closed shape?
cup
# What methods exist for returning all points within an arbitrary closed shape?

(Asked by: username_0 on 2011-10-13)

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?

**Tags:** cg.comp-geom, range-searching
> **Comments:**
> **username_1**: Have you tried Google?  
> **username_2**: It's not clear to me if you really want range search in your application.  

---

## 1 answers

### Answer by username_3 on 2011-10-13. Score: 8

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.


---

