Best of Two Worlds: Combining High and Low Resolution to Compute Viewsheds on terrains

The viewshed of a point $v$ on a grid terrain $T$, viewshed${}_T(v)$, is defined as the set of grid points in $T$ that are visible from $v$. We describe a novel algorithm for computing viewshed${}_T(v)$ using a multi-resolution approach: Given a parameter $k>1$ that represents the block size, we create a grid $T^{\mathrm{\prime }}$ which is a lower-resolution version of $T$, such that each point in $T^{\mathrm{\prime }}$ corresponds to a block of $\lceil \sqrt{k}\rceil$-by-$\lceil \sqrt{k}\rceil$ points in $T$. The key of our approach is using $T^{\mathrm{\prime }}$ to speed up the computation of viewshed${}_T(v)$ while not introducing approximation. We compute viewshed${}_T(v)$ in two steps: First we compute the viewshed of $v$ on $T^{\mathrm{\prime }}$, while maintaining the invariant that any block in $T^{\mathrm{\prime }}$ that is labeled as invisible may not contain any visible points. Thus, the first step’s role is to use $T^{\mathrm{\prime }}$ to filter out blocks in $T$ that are guaranteed to be invisible. The second step considers the blocks that were labeled as visible in $T^{\mathrm{\prime }}$ and computes the visibility of their points with full accuracy using the data in $T$. Overall the algorithm runs in $O(n+\frac{n}{k}\lg \frac{n}{k}+k\lg k+l\cdot \lg n)$, where $l$ is the total size of visible blocks in $T^{\mathrm{\prime }}$. When $k=\mathrm{\Omega }(1)$ and $l=o(n)$, the running time of our algorithm improves on the previous best bound of $O(n\lg n)$. Our experimental results show the performance of the new algorithm in practice and a speedup of more than an order of magnitude compared to previous algorithms.