A certifying algorithm is an algorithm that produces, with each output, a certificate or witness
(easy-to-verify proof) that the particular output has not been compromised by a bug. A user …

The convex hull of a set of points is the smallest convex set that contains the points. This
article presents a practical convex hull algorithm that combines the two-dimensional …

We describe our experience with a new algorithm for the reconstruction of surfaces from
unorganized sample points in IR3. The algorithm is the first for this problem with provable …

The topic of this chapter, Voronoi diagrams, differs from other areas of computational
geometry, in that its origin dates back to the 17th century. In his book on the principles of …

The observation that mid-ocean ridge basalts had~ 3× higher iodine/plutonium ratios
(inferred from xenon isotopes) compared to ocean island basalts holds critical insights into …

We present a randomized strategy for maintaining balance in dynamically changing search
trees that has optimal expected behavior. In particular, in the expected case a search or an …

Given a collection S of subsets of some set U, and M⊂ U, the set cover problem is to find the
smallest subcollection C⊂ S such that M is a subset of the union of the sets in C. While the …

In this paper we address the problem of segmenting a trajectory based on spatiotemporal
criteria. We require that each segment is homogeneous in the sense that a set of …

The resource constrained shortest path problem (CSP) asks for the computation of a least
cost path obeying a set of resource constraints. The problem is NP-complete. We give …

The “convex hull problem” is a catch-all phrase for computing various descriptions of a
polytope that is either specified as the convex hull of a finite point set in Rd or as the …