"Smart pixels" are sensor pixels which have been imbued with a limited amount of processing power. Consider a model of computation in which a grid of these smart pixels can perform simple arithmetic, store a small amount of data, and communicate with their direct neighbors. In this video, we review recent algorithms for well-known geometric problems developed within such a model. Specifically, given a black-and-white image on a w by h grid of smart pixels, we show how the sizes, orientations, centers of gravity, and convex hulls of multiple objects on the grid can be computed simultaneously in time O(w + h).

We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes O(n log n + m) time, where n is the input size and m is the output size. This is the first time-optimal Delaunay refinement algorithm.

An effective method in practice to compute quality Delaunay triangulations is to apply parallel refinements that insert Steiner points whose prestars in the triangulation do not overlap. We show that these algorithms can be implemented in O(logm) time using m processors, where m is the output size. To our knowledge, this is the first such analysis. Categories and Subject Descriptors F.2.2 [Nonnumerical Algorithms and Problems]: Geo-metrical problems and computations; G.2.m [Discrete Math-

A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and ubiquitous in 3-dimensional Delaunay triangulations. Even when the point-set is well-spaced, slivers may result. This paper shows that such a point set permits a small perturbation whose Delaunay triangulation contains no slivers. It also gives deterministic algorithms that compute the perturbation of n points in time O(n log n) with one processor and in time O(log n) with O(n) processors. Keywords. Mesh generation, computational geometry, tetrahedral meshes, Delaunay triangulations, slivers, mesh smoothing, mesh clean-up. 1. INTRODUCTION This paper presents a smoothing and clean-up algorithm for 3-dimensional Delaunay triangulations that removes all slivers. A necessary assumption of the algorithm is that the input triangles and tetrahedra have a bounded circumradius to shortest edge length...