New Voices and New Visions for Engaging Native Americans in Computer Science is a collaborative project between Boston University and University of New Mexico, funded through NSF's Broadening Participation in Computing program. This project combines Native American culture and art with a high-technology, computer-rich environment as a vehicle to engage Native American students in computer and computational science. The project employs the Access Grid (AG), virtual reality technologies and Boston University's stereoscopic Deep Vision Display Wall (DVD Wall) to create a culturally and technologically compelling educational experience.The curriculum will expose both college and high school students to the power and depth of computer science, hopefully inspiring many of them to obtain a degree in this discipline. We anticipate that this pilot project will provide a model based on an interdisciplinary framework which can be emulated by other institutions and adapted for other groups underrepresented in computer and computational sciences.

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes.

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds of O(log n log * n) time and n²/log n processors. We generalize this to obtain an O(logn log* n) time algorithm using n^d/logn processors for solving the problem in d dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrange-ment of n lines on-line, in which each insertion is done in optimal O(logn) time using n / log n processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.

We develop a representation for the topological structure of subdivided manifolds (with and without boundary) of dimension d ≥ 1 which allows straightforward access of the available order information. It is shown that there exists a large amount of ordering information in subdivided manifolds: given a (k-2)-cell in the boundary of a (k+1)-cell, 1 ≤ k ≤ d, all of the k- and (k-1)-cells 'between them' can be ordered 'around' the (k-2)-cell. This includes the usual orderings in 2- and 3-dimensional objects. We introduce the 'cell-tuple structure', a simple, uniform representation of the incidence and ordering information in a subdivided manifold. It includes the quad-edge data structure of Guibas and Stolfi [GS 85] and the facet-edge data structure of Dobkin and Laszlo [DL 87] as special cases in dimensions 2 and 3, respectively.