ρ-Significant Range Queries
Gregory Bint

Traditionally, geometric range queries are interested in finding objects which fall within a query region, e.g., points in a circle, line segments in a rectangle. If we are given a query region $$Q$$, and an object $$o$$, $$o$$ should be considered if $$o \in Q$$.

We consider a related problem where we wish to report objects which may be only partially within the query region. That is, given a query region $$Q$$ and a fixed parameter $$\rho$$, $$0 < \rho \leq 1$$, we want to identify all objects where the proportion of the object found inside $$Q$$ is at least $$\rho$$ w.r.t. the size, area, etc. of the original object. E.g., for a line segment $$s$$, we would include $$s$$ if and only if $$|s \cap Q| \geq \rho |s|$$.

We will give the details for several specific variations of the problem.