Summary form only given, as follows. One of the central questions in topology is determining whether a given curve is knotted or unknotted. An algorithm to decide this question was given by Haken (1961), using the technique of normal surfaces. These surfaces are rigid, discretized surfaces, well suited for algorithmic analysis. Any oriented surface without boundary can be obtained from a sphere by adding "handles". The number of handles is called the genus of the surface, and the smallest genus of a spanning surface for a curve is called the genus of the curve. A curve has genus zero if and only if it is unknotted. Schubert extended Haken's work, giving an algorithm to determine the genus of a curve in any 3-manifold. We examine the problem of deciding whether a polygonal knot in a closed triangulated three-dimensional manifold bounds a surface of genus at most g, 3-MANIFOLD KNOT GENUS. Previous work of Hass, Lagarias and Pippenger had shown that this problem is in PSPACE. No lower bounds on the running time were previously known. We show that this problem is NP-complete.

We show that the problem of deciding whether a polygonal knot in a closed three-dimensional manifold bounds a surface of genus at most g is NP-complete.

A collection of n balls in d dimensions forms a k -ply system if no point in the space is covered by more than k balls. We show that for every k -ply system Γ, there is a sphere S that intersects at most O ( k 1/ d n 1−1/ d ) balls of Γ and divides the remainder of Γ into two parts: those in the interior and those in the exterior of the sphere S , respectively, so that the larger part contains at most (1−1/( d +2)) n balls. This bound of ( O ( k 1/ d n 1−1/ d ) is the best possible in both n and k . We also present a simple randomized algorithm to find such a sphere in O(n) time. Our result implies that every k -nearest neighbor graphs of n points in d dimensions has a separator of size O ( k 1/ d n 1−1/ d ). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space.

A derivation in a transformational system such as a graph grammar may be redundant in the sense that the exact order of the transformations may not affect the final outcome; all that matters is that each transformation, when applied, is applied to the correct substructure. By taking advantage of this redundancy, we can develop an efficient encoding scheme for such derivations. This encoding scheme has a number of diverse applications. It can be used in efficient enumeration of combinatorial objects or for compact representation of program and data structure transformations. It can also be used to derive lower bounds on lengths of derivations. It is shown, for example, that $\Omega ( n \log n )$ applications of the associative and commutative laws are required in the worst case to transform an n-variable expression over a binary associative, commutative operation into some other equivalent expression. Similarly, it is shown that $\Omega ( n\log n )$ “diagonal flips” are required in the worst case to transform one n-vertex numbered triangulated planar graph into some other one. Both of these lower bounds have matching upper bounds. An $O( n\log n )$ upper bound for associative, commutative operations was known previously, whereas here an $O( n\log n )$ upper bound for diagonal flips is obtained.

We show that every graph that is the 1-skeleton of a simplicial complex K in 3-dimensions has a separator of size O(c 2/3 + ~), where c is the number of 3-simplexes in K and 0 is the number of 0simplexes on the boundary of K, if every 3-simplex has bounded aspect-ratio.This is natural generalization of the separator results for planar graphs, such as the Lipton and Tarjan planar separator theorem.We also show that a family of separators of size O(c 2/3) exists and is constructible.Using this family of separators we get an O(n 2) time algorithm for solving linear systems that arise from the finite element method.In particular, we solve linear systems in O(n 2) time where the underlying graph is the 1-skeleton of a simplicial complex having bounded aspect-ratio and small boundary.All the constructions work in RNC with a reasonably small number of processors.

We present a method for tracing a curve that is represented as the contour of a function in Euclidean space of any dimension. The method proceeds locally by following the intersections of the contour with the facets of a triangulation of space. The algorithm does not fail in the presence of high curvature of the contour; it accumulates essentially no round-off error and has a well-defined integer test for detecting a loop. In developing the algorithm, we explore the nature of a particular class of triangulations of Euclidean space, namely, those generated by reflections.

Computer Science Department