# GCP Placement

## Algorithms

#### Version 0.612th Apr, 2019

Based on our experiments, we design algorithms for GCP placement based on the coverage radius. In particular, we provide algorithms for:

• Coverage Estimation. Given existing AOI, and GCPs, compute the coverage radius of the GCPs. This allows quality check of GCPs placed on site.

• GCP Placement. Given an AOI, and a coverage radius, compute a placement of GCPs with the given coverage. This enables placement of GCPs in both new sites, and sites with a few existing GCPs.

Notation. We think of a region as a subset of the 2-D plane, with a positive area. We represent regions by caligraphic letters: $\aoi, \X,$ etc. The area of a region is denoted by $\area(\cdot)$. The ball of radius R around a point p is represented by $\ball(p, R).$

# 1Coverage and Heatmaps

We address the simpler question of estimating the coverage of a given set of GCPs, $\gcps$ within an AOI $\aoi.$ The region covered by a single point $p \in \aoi$ upto radius $R$ is $\ball(p, R).$ Thus, the total region covered by the GCPs upto radius R, gives the “heatmap” of the GCPs at radius R:

(1)$\heat(\gcps, \aoi, R) \defeq \paren{\bigcup_{p \in \gcps} \ball(p, R)} \bigcap \aoi.$

This provides a ready-to-compute formula for generating heatmap vizualizations. To compute the coverage radius of a set of GCPs, we perform a binary-search using the above formula. As the coverage radius may be an arbitrary real number, we estimate it upto an error $\epsilon.$

Algorithm 1.EstimateCoverage

Input. The AOI, $\aoi$; a set of GCPs, $\gcps$; and an error threshold $\epsilon.$
Output. The coverage radius $R$, upto error $\pm \epsilon.$

1. set $l = 0, h = 2\operatorname{\mathsf{diam}}(\aoi).$
2. set $m = (l+h)/2.$
3. while $h - l > \epsilon$:
1. set $\aoi' = \aoi \setminus \bigcup_{g \in \gcps} \ball(g, m).$
2. if $\aoi'$ is empty: set $h = m$, otherwise set $l = m.$
3. set $m = (l+h)/2.$
4. return m

# 2GCP Placement

Our GCP placement problem is a version of Geometric Set Cover. Determining the minimum GCPs (and their positions), is hard and thus we settle for an approximation algorithm. The algorithm begins with the initial AOI, denoted $\aoi$, and iteratively places GCPs, while updating the remaining region of the AOI to be covered.\$

The iterative procedure picks the position of the next GCP by randomly sampling from a distribution that prioritizes positions that cover maximum area.[1] The coverage of a point p on $\aoi$, denoted $\X(p, \aoi)$ is defined as:

(2)$\X(p, \aoi) \defeq \ball(p, R) \cap \aoi.$

The distribution, denoted $\dist(\aoi),$ samples a point $p \in \aoi$ proportional to the area of its coverage, denoted $\area(\X(p, \aoi)).$

We describe the placement algorithm assuming we can sample from the distribution $\dist(\aoi).$ The sampling sub-routine uses a few algorithmic techniques and is described in the rest of the section.

Algorithm 2.GCP Placement

Input. The AOI, $\aoi$; coverage radius $R$; and an error threshold $\epsilon.$
Output. Collection of GCPs, $\gcps.$

1. set $\gcps = \emptyset$
2. set $\aoi' = \aoi$
3. while $\area(\aoi') > \epsilon$:
1. sample $p$ from $\dist(\aoi')$
2. add $p$ to $\gcps$
3. set $\aoi' = \aoi' \setminus \X(p)$
4. return m

## 2.1Uniform Sampling in $\aoi$

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).

## 2.2Sampling From $\dist(\aoi)$

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

## 2.3Estimate $C(\aoi)$

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.

## 2.4Tuning Confidence

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. ↩︎