Abstract
We describe a novel application of the distribution sweeping technique to computing visibility on terrains. Given an arbitrary viewpoint v, the basic problem we address is computing the visibility map or viewshed of v, which is the set of points in the terrain that are visible from v. We give the first I/Oefficient algorithm to compute the viewshed of v on a grid terrain in external memory. Our algorithm is based on Van Kreveld’s O(n lg n) time algorithm for the same problem in internal memory. It uses O(sort(n)) I/Os, where sort(n) is
the complexity of sorting n items of data in the I/O-model. We present an implementation and experimental evaluation of the algorithm. Our implementation clearly outperforms the previous (in-memory) algorithms and can compute visibility for terrains of up to 4GB in a few hours on a low-cost machine.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2007) 6 January 2007, New Orleans, Louisiana, USA |
| Place of Publication | Philadelphia, Pennsylvania, USA |
| Publisher | Society for Industrial and Applied Mathematics (SIAM) |
| Pages | 13-22 |
| Publication status | Published - 2007 |
| Event | 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007) - Astor Crowne Plaza Hotel, New Orleans, United States Duration: 6 Jan 2007 → 6 Jan 2007 Conference number: 9 http://www.siam.org/meetings/alenex07/ |
Workshop
| Workshop | 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007) |
|---|---|
| Abbreviated title | ALENEX 2007 |
| Country/Territory | United States |
| City | New Orleans |
| Period | 6/01/07 → 6/01/07 |
| Other | Event preceded the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07) |
| Internet address |