Abstract We present a method for removing unwanted topological features (e.g., islands, handles, cavities) from a sequence of shapes where each shape is nested in the next. Such sequences can be found in nature, such as a multi‐layered material or a growing plant root. Existing topology simplification methods are designed for single shapes, and applying them independently to shapes in a sequence may lose the nesting property. We formulate the nesting‐constrained simplification task as an optimal labelling problem on a set of candidate shape deletions (“cuts”) and additions (“fills”). We explored several optimization strategies, including a greedy heuristic that sequentially propagates labels, a state‐space search algorithm that is provably optimal, and a beam‐search variant with controllable complexity. Evaluation on synthetic and real‐world data shows that our method is as effective as single‐shape simplification methods in reducing topological complexity and minimizing geometric changes, and it additionally ensures nesting. Also, the beam‐search strategy is found to strike the best balance between optimality and efficiency.

We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O(n2) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O(n4) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

We present a novel algorithm for computing the medial axes of 3D shapes. We make the observation that the medial axis of a voxel shape can be simply yet faithfully approximated by the interior Voronoi diagram of the boundary vertices, which we call the voxel core. We further show that voxel cores can approximate the medial axes of any smooth shape with homotopy equivalence and geometric convergence. These insights motivate an algorithm that is simple, efficient, numerically stable, and equipped with theoretical guarantees. Compared with existing voxel-based methods, our method inherits their simplicity but is more scalable and can process significantly larger inputs. Compared with sampling-based methods that offer similar theoretical guarantees, our method produces visually comparable results but more robustly captures the topology of the input shape.

While playing a fundamental role in shape understanding, the medial axis is known to be sensitive to small boundary perturbations. Methods for pruning the medial axis are usually guided by some measure of significance. The majority of significance measures over the medial axes of 3D shapes are locally defined and hence unable to capture the scale of features. We introduce a global significance measure that generalizes in 3D the classical Erosion Thickness (ET) measure over the medial axes of 2D shapes. We give precise definition of ET in 3D, analyze its properties, and present an efficient approximation algorithm with bounded error on a piece-wise linear medial axis. Experiments showed that ET outperforms local measures in differentiating small boundary noise from prominent shape features, and it is significantly faster to compute than existing global measures. We demonstrate the utility of ET in extracting clean, shape-revealing and topology-preserving skeletons of 3D shapes.

In this paper techniques from persistent homology are generalized to homotopy groups and to algebraic invariants from knot theory. We define the persistent Alexander module, which can be used to detect knotting in a complex and determine when the knotting changes when viewed from different scales. Algorithms that use the persistent Alexander module are also presented and applied to examples including protein structures. While the basic definition of persistent homotopy is known, this is the first work to use it successfully for computations.

Abstract Thinning is a commonly used approach for computing skeleton descriptors. Traditional thinning algorithms often have a simple, iterative structure, yet producing skeletons that are overly sensitive to boundary perturbations. We present a novel thinning algorithm, operating on objects represented as cell complexes, that preserves the simplicity of typical thinning algorithms but generates skeletons that more robustly capture global shape features. Our key insight is formulating a skeleton significance measure, calledmedial persistence, which identify skeleton geometry at various dimensions (e.g., curves or surfaces) that represent object parts with different anisotropic elongations (e.g., tubes or plates). The measure is generally defined in any dimensions, and can be easily computed using a single thinning pass. Guided by medial persistence, our algorithm produces a family of topology and shape preserving skeletons whose shape and composition can be flexible controlled by desired level of medial persistence.

We describe cs1graphics, a new Python drawing package designed with pedagogy in mind. The package is simple enough that students can sit down and make use of it from the first day of an introductory class. Yet it provides seamless support for intermediate and advanced lessons as students progress. In this paper, we discuss its versatility in the context of an introductory course. The package is available at www.cs1graphics.org.

There is an ongoing debate regarding the role of object orientation in the introductory programming sequence. While the pendulum swings to and fro between the "objects first" and "back to basics" extremes, there is general agreement that object-oriented programming is central to modern software development and therefore integral to a computer science curriculum. Developing effective approaches to teach these principles raises challenges that have been exacerbated by the use of Java or C++ as the first instructional language.

We demonstrate the use of a new Python graphics package named cs1graphics, while discussing its impact on pedagogy and showcasing the recent work of our students. Our package was originally developed with two goals in mind. First, we insisted that it be intuitive enough that students can sit down and make use of it from the very first day of an introductory class. Second, we wanted to provide seamless support for intermediate and advanced lessons as students progress. The resulting package is freely available at www.cs1graphics.org. We find its combination of simplicity and functionality unmatched by existing packages.

Incorporating advanced programming concepts into an introductory programming course has to be done carefully to avoid overwhelming the students. We describe our experiences doing network programming in a CS1 course taught in Python. The simplicity of the built-in libraries allowed a fair amount of networking to be introduced in a week-long module of the course. In this short time we had the students writing both multithreaded clients and servers.

Python's use in education has grown rapidly, due to its elegantly simple syntax. Though often viewed as a "scripting language," Python is a fully object-oriented language with an extremely consistent object model and a rich set of built-in classes.

We investigate the use of a thin-client based configuration in providing students with universal access to a centralized, graphical computing environment. The primary goal is to enable students to work effectively from arbitrary locations and computing platforms, while always interacting with the consistent environment seen in tightly controlled labs.

For a sufficiently dense set of points in any closed Riemannian manifold, we prove that a unique Delannay triangulation exists.This triangulation has the same properties as in Euclidean space.Algorithms for constructing these triangulations will also be described.

We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise, depending on its life-time or persistence within the filtration. We give fast algorithms for completing persistence and experimental evidence for their speed and utility.