The ability to use computational tools to collect, organize, visualize, and analyze data is a valuable skill both inside and outside of computer science. In this paper we describe the design and implementation of a statistics-infused introduction to computer science, developed in collaboration with statistics faculty, at St. Olaf College. We propose that there exists a growing demographic of 'data-centric' students who expect to write small amounts of code in the context of work in other fields, and who are eager to take a CS course adapted to their needs. This particular data-centric CS1 course has been a catalyst for collaboration between faculty in multiple fields and multiple institutions.

This work presents a powerful variant of the ICP (iterative closest point) algorithm for registering range images using a probability field. The probability field (p-field) represents the probability distribution of the surface position. By capitalizing on the properties of the range image, fast construction, compact representation, and efficient query of the p-field can be achieved. Different sensor models are supported by the p-field according to the properties of the range image. Range images can be precisely aligned by maximizing the probability of overlapping surfaces via the p-field.

We study the problem of computing the visibility graph defined by a set P of n points inside a polygon Q: two points p,q ε P are joined by an edge if the segment ‾pq ⊂ Q. Efficient output-sensitive algorithms are known for the case in which P is the set of all vertices of Q. We examine the general case in which P is an arbitrary set of points, interior or on the boundary of Q and study a variety of algorithmic questions. We give an output-sensitive algorithm, which is nearly optimal, when Q is a simple polygon. We introduce a notion of "fat" or "robust" visibility, and give a nearly optimal algorithm for computing visibility graphs according to it, in polygons Q that may have holes. Other results include an algorithm to detect if there are any visible pairs among P, and algorithms for output-sensitive computation of visibility graphs with distance restrictions, invisibility graphs, and rectangle visibility graphs.

In a landmark survey of visibility algorithms in 1974, Sutherland, Sproull, and Schumacker stated that "We believe the principal untappedsource of help for hidden surface algorithms lies in frame and object coherence." Making use of such temporal coherence appears to be difficult, however, for scenes with moving objects. Almost three decades later Cohen-Or, Chrysanthou, and Silva stated that "The efficient handing of dynamic scenes is an open area of research at this point." This five minute video describes a kinetic visibility algorithm formoving objects in the plane that is provably efficient in an average case setting.

The digitization of the 3D shape of real objects is a rapidly expanding field, with applications in entertainment, design, and archaeology. We propose a new 3D model acquisition system that permits the user to rotate an object by hand and see a continuously-updated model as the object is scanned. This tight feedback loop allows the user to find and fill holes in the model in real time, and determine when the object has been completely covered. Our system is based on a 60 Hz. structured-light rangefinder, a real-time variant of ICP (iterative closest points) for alignment, and point-based merging and rendering algorithms. We demonstrate the ability of our prototype to scan objects faster and with greater ease than conventional model acquisition pipelines.

We present a novel approach to real-time structured light range scanning. After an analysis of the underlying assumptions of existing structured light techniques, we derive a new set of illumination patterns based on coding the boundaries between projected stripes. These stripe boundary codes allow range scanning of moving objects, with only modest assumptions about scene continuity and reflectance. We describe an implementation that integrates these new codes with real-time algorithms for tracking stripe boundaries and determining depths. Our system uses a standard video camera and DLP projector, and produces dense range images at 60 Hz with 100 /spl mu/m accuracy over a 10 cm working volume. As an application, we demonstrate the creation of complete models of rigid objects: the objects are rotated in front of the scanner by hand, and successive range images are automatically aligned.