Pastel
PastelGeometry
Geometric algorithms
Range searching

Range searching

A set $S$ is multi-ordered if it comes with $d$ strict weak orders $<_1, ..., <_d subset S^2$ , for some integer $d$ . A multi-interval in $S$ is a set of the form $I = cap_{i = 1}^d I_i$ , where $I_i subset S$ is an interval in $S$ with respect to $<_i$ . Range searching is the problem of reporting the set $P cap I$ , for a given multi-interval $I$ . Range counting is the problem of reporting the integer $|P cap I|$ , for a given multi-interval $I$ .

Usual definition

Our definition is more general than usual. The usual definition is recovered by setting $S = RR^d$ and $x <_i y <=> x_i < y_i$ . In this case a multi-interval becomes an axis-aligned box, also called an orthogonal range. Our definition can be used also for non-orthogonal range searching. One such example is given by $S = RR^2$ , $x <_1 y <=> x_1 < y_1$ , and $x <_2 y <=> x_1 + x_2 < y_1 + y_2$ .

Range searching

Usual definition

Learn more

Files

An aggregate file for range searching.