The viewshed of a point v on a grid terrain T, viewshedT (v), is the set of grid points in T that are visible from v. We describe a novel algorithm for computing viewshedT (v) using a multiresolution approach: Given a parameter k > 1 that represents the block size, we create a grid T′ which is a lower-resolution version of T, such that each point in T corresponds to a block of [EQUATION] points in T; T′ has size Θ(n/k), where n is the size of the original grid. The key of our approach is using T′ to speed up the computation of viewshedT(v) while not introducing approximation. We compute viewshedT(v) in two steps: First we compute the viewshed of v on T'′, while maintaining the invariant that any block in T′ that is labeled as invisible may not contain any visible points. Thus, the first step's role is to use T′ 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′ and computes the visibility of their points with full accuracy using the data in T. Overall the algorithm runs in O[EQUATION], where l is the total size of visible blocks in T′. When k > 1 and l = o(n), the running time of our algorithm improves on the previous best bound of O(n lg n) [9, 15]. We describe a suite of experimental results showing the performance of our algorithm in practice and a speedup of more than an order of magnitude compared to previous algorithms.

While previous research has investigated psychological factors in introductory programming courses, only little is known about their impact in algorithms courses. Similarly, despite the importance of collaborative problem solving in both academic and non-academic settings, only a small number of studies reports on group work in domains other than programming. In our case study, we focused on the labs of an introductory algorithms course. We measured the cognitive load of the lab assignments as well as the students' emotional reaction to them. We connect these observations to self-efficacy, performance, psychological traits, and help-seeking behavior as well as to the insights gained from a comprehensive set of follow-up interviews. Even though our study is a small-scale study, the results from applying both quantitative and qualitative methods frame directions for both pedagogic interventions and further (revalidation) studies related to the connection of non-cognitive factors, learning experiences, and performance in collaborative algorithms labs.

We report on the development and validation of an instrument to assess self-efficacy in an introductory algorithms course. The instrument was designed based upon previous work by Ramalingam and Wiedenbeck and evaluated in a multi-institutional setup. We performed statistical evaluations of the scores obtained using this instrument and compared our findings with validated psychometric measures. These analyses show our findings to be consistent with self-efficacy theory and thus suggest construct validity.

Given a terrain T and a point v, the viewshed or visibility map of v is the set of points in T that are visible from v. To decide whether a point p is visible one needs to interpolate the elevation of the terrain along the line-of-sight (LOS) vp. Existing viewshed algorithms differ widely in which and how many points they chose to interpolate, how many lines-of-sight they consider, and how they interpolate the terrain. These choices crucially affect the running time and accuracy of the algorithms. In this paper our goal was to obtain an IO-efficient algorithm that computes the viewshed on a grid terrain with as much accuracy as possible given the resolution of the data. We describe two algorithms which are based on computing and merging horizons, and we prove that the complexity of horizons on a grid of n points is O(n), improving on the general O(nα(n)) bound on triangulated terrains. Our finding is that, in practice, horizons on grids are significantly smaller than their theoretical worst case bound, which makes horizon-based approaches very fast. To measure the differences between viewsheds computed with various algorithms we implement an error metric that averages differences over a large number of viewsheds computed from a set of viewpoints with topological significance, like valleys and ridges. Using this metric we compare our current approach, Van Kreveld's model used in our previous work [7], the algorithm of Ferreira et al. [6], and the viewshed module r.los in the open source GIS GRASS.

This paper describes the design and engineering of algorithms for computing visibility maps on massive grid terrains. Given a terrain T, specified by the elevations of points in a regular grid, and given a viewpoint v, the visibility map or viewshed of v is the set of grid points of T that are visible from v. We describe three new algorithms to compute the viewshed for any given terrain T and viewpoint v.

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/O-efficient 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 4 GB in a few hours on a low-cost machine.

We present algorithms that solve a number of fundamental problems on planar directed graphs (planar digraphs) in O((N)) I/Os, where (N) is the number of I/Os needed to sort N elements. The problems we consider are breadth-first search, the single-source shortest path problem, computing a directed ear decomposition of a strongly connected planar digraph, computing an open directed ear decomposition of a strongly connected biconnected planar digraph, and topologically sorting a planar directed acyclic graph.