Algorithms for ε-Approximations of Terrains

Consider a point set

${\mathcal{D}}$

with a measure function

$\mu : {\mathcal{D}} \to \mathcal{R}$

. Let

${\mathcal{A}}$

be the set of subsets of

$\mathcal{D}$

induced by containment in a shape from some geometric family (e.g. axis-aligned rectangles, half planes, balls,

k

-oriented polygons). We say a range space

$(\mathcal{D}, \mathcal{A})$

has an

ε

-approximation

P

if

$$\max_{R \in \mathcal{A}} \left| \frac{\mu(R \cap P)}{ \mu(P)} - \frac{\mu(R \cap \mathcal{D})}{ \mu(\mathcal{D})} \right| \leq \varepsilon.$$

We describe algorithms for deterministically constructing discrete

ε

-approximations for continuous point sets such as distributions or terrains. Furthermore, for certain families of subsets

$\mathcal{A}$

, such as those described by axis-aligned rectangles, we reduce the size of the

ε

-approximations by almost a square root from

$O(\frac{1}{\varepsilon^2} \log \frac{1}{\varepsilon})$

to

. This is often the first step in transforming a continuous problem into a discrete one for which combinatorial techniques can be applied. We describe applications of this result in geospatial analysis, biosurveillance, and sensor networks.