We construct a sampler for the distribution $\dist(\aoi)$ by first sampling uniformly within the region $\aoi$; and then converting this to the required distribution. The first step is a simple application of rejection sampling, and is described below.

Algorithm 3.Uniform Region Sample

Input. The region, $\aoi.$
Output. A point $p \in \aoi$ picked uniformly at random.

1. set bbox = bounding box of $\aoi$
2. while yet to sample:
   1. sample $p$ uniformly from bbox
   2. if $p \in \aoi$: break from loop; else continue
3. return p

The bounding box may be any superset of the region $\aoi$, where a uniform sampling is easy to obtain. For instance, we may use the minimum axis parallel rectange covering the AOI; to uniformly sample point in the bounding box, we sample a random number between the left and right bounds, and another between the top and bottom bounds. Note that the sample in step (i) of the loop is uniform in the bounding box, and thus is uniform in $\aoi$ when conditioned on falling inside the region as done in step (ii).

The sampler for $\dist(\aoi)$ is a more sophisticated application of rejection sampling. Denoting area of $\aoi$ by $\area(\aoi)$, the uniform distribution over $\aoi$ has prob. density function (pdf):

(3)$f(p) = \frac{1}{\area(\aoi)}.$

On the other hand, the distribution $\dist(\aoi)$ has a pdf:

(4)$g(p) = \frac{\area(\X(p, \aoi))}{\mu(\aoi)\cdot C(\aoi)},$

where $C(\aoi)$ is the normalization constant:

(5)$C(\aoi) = \int_{\aoi} \frac{\area(\X(p, \aoi))}{\area(\aoi)} = \exp \brac{\area(\X(p, \aoi))} .$

Finally, let $G \ge \sup_\aoi \curly{\frac{g(p)}{f(p)}}$ be an upper bound on the maximum ratio of the two distributions. Then, the following algorithm samples from $\dist(\aoi)$ using the uniform sampler constructed earlier.

Algorithm 4.Coverage Sampler

Input. The region, $\aoi.$
Output. A point $p$ sampled from $\dist(\aoi).$

1. while yet to sample:
   1. sample $p$ uniformly in $\aoi$
   2. accept and break with probability $\frac{g(p)}{G \cdot f(p)}$
2. return p

The coverage sampler algorithm, described above, requires estimating $C(\aoi)$, and using it, the coefficient $G$. We estimate $C(\aoi)$ by computing the expectation in equation (4) at uniform random samples in $\aoi$. To estimate the confidence and accuracy of this estimate, note that $\mu(\X(p))$ for $p \in \aoi$ satisfies:

(6)$0 \le \mu(\X(p)) \le \pi R^2.$

Then, using Hoeffding’s Inequality the probability of the average of $n$ samples, denoted $C_n(\aoi)$, not falling within $\pm\epsilon$ of $C(\aoi)$ is:

(7)$\prob\curly{ \left\lvert C_n(\aoi) - C(\aoi) \right\rvert \ge \epsilon} \le 2 \operatorname{exp}\paren{\frac{-2n\epsilon^2} {\pi^2 R^4}} .$

Thus, we get an additive $\epsilon$-approximation with probability $1 - \delta$ by picking $n$ larger than $\frac{\pi^2 R^4}{2\epsilon^2} \log\paren{\frac{2}{\delta}}.$ This yields the following Monte-Carlo algorithm to estimate $C(\aoi)$.

Algorithm 5.Estimate Ball Integral

Input. The region, $\aoi$, error threshold $\epsilon$, and confidence parameter $\delta$.
Output. Estimate of $C(\aoi)$.

1. Compute $n = \left\lceil \frac{\pi^2 R^4}{2\epsilon^2} \log\paren{\frac{2}{\delta}} \right\rceil$.
2. set sum = 0
3. for i = $1 \ldots n$:
   1. sample $p$ uniformly in $\aoi$
   2. set sum = sum + $\mu(\X(p, \aoi))$
4. return sum / n

Finally, we get a lower bound on the max ratio:

(8)$G = \frac{\pi R^2}{C_n(\aoi) - \epsilon}$

where $C_n$ is the estimate using algorithm above, with $\epsilon$ the error threshold.

Due to algorithm 5, our overall algorithm for placement is Monte-Carlo in nature. In particular, assuming we place k GCPs in total, the probability that the placement went by plan is $1 - k \delta$.

We obtain a bound on $k$ as follows: the GCPs picked by our placement are at least distance $R$ from other GCPs. Thus, $R/2$ radius balls around the GCPs are disjoint. Together, they may, at best, cover the aoi $\aoi$ padded by radius $R/2$: $\aoi + B(0, R/2).$ Thus:

(9)$k \le \frac{4\cdot\area(\aoi + B(0, R/2))}{\pi R^2}.$

Thus, to get a 90% confidence algorithm, we may set:

(10)$\delta \le 1/10k \le \frac{\pi R^2}{40 \cdot\area(\aoi + B(0, R/2))}.$

---

1. A greedy strategy is known to yield poorer results on an average. ↩︎