Abstract We describe a new method for approximating an implicit surface F by a piecewise‐flat triangulated surface whose triangles are as close as possible to equilateral. The main advantage is improved mesh quality which is guaranteed for smooth surfaces. The GradNormal algorithm generates a triangular mesh that gives a piecewise‐differentiable approximation of F, with angles between 35.2 and 101.5 degrees. As the mesh size approaches 0, the mesh converges to F through surfaces that are isotopic to F.

A new algorithm is presented that provides a constructive way to conformally warp a triangular mesh of genus zero to a destination surface with minimal metric deformation, as well as a means to compute automatically a measure of the geometric difference between two surfaces of genus zero. The algorithm takes as input a pair of surfaces that are topological 2-spheres, each surface given by a distinct triangulation. The algorithm then constructs a map $(f)$ between the two surfaces. First, each of the two triangular meshes is mapped to the unit sphere using a discrete conformal mapping algorithm. The two mappings are then composed with a Möbius transformation to generate the function $(f)$. The Möbius transformation is chosen by minimizing an energy that measures the distance of $(f)$ from an isometry. We illustrate our approach using several "real life" data sets. We show first that the algorithm allows for accurate, automatic, and landmark-free nonrigid registration of brain surfaces. We then validate our approach by comparing shapes of proteins. We provide numerical experiments to demonstrate that the distances computed with our algorithm between low-resolution, surface-based representations of proteins are highly correlated with the corresponding distances computed between high-resolution, atomistic models for the same proteins.

BACKGROUND: The problem of determining the physical conformation of a protein dimer, given the structures of the two interacting proteins in their unbound state, is a difficult one. The location of the docking interface is determined largely by geometric complementarity, but finding complementary geometry is complicated by the flexibility of the backbone and side-chains of both proteins. We seek to generate candidates for docking that approximate the bound state well, even in cases where there is backbone and/or side-chain difference from unbound to bound states. RESULTS: We divide the surfaces of each protein into local patches and describe the effect of side-chain flexibility on each patch by sampling the space of conformations of its side-chains. Likely positions of individual side-chains are given by a rotamer library; this library is used to derive a sample of possible mutual conformations within the patch. We enforce broad coverage of torsion space. We control the size of the sample by using energy criteria to eliminate unlikely configurations, and by clustering similar configurations, resulting in 50 candidates for a patch, a manageable number for docking. CONCLUSIONS: Using a database of protein dimers for which the bound and unbound structures of the monomers are known, we show that from the unbound patch we are able to generate candidates for docking that approximate the bound structure. In patches where backbone change is small (within 1 Å RMSD of bound), we are able to account for flexibility and generate candidates that are good approximations of the bound state (82% are within 1 Å and 98% are within 1.4 Å RMSD of the bound conformation). We also find that even in cases of moderate backbone flexibility our candidates are able to capture some of the overall shape change. Overall, in 650 of 700 test patches we produce a candidate that is either within 1 Å RMSD of the bound conformation or is closer to the bound state than the unbound is.

Given any knot diagram E, we present a sequence of knot diagrams of the same knot type for which the minimum number of Reidemeister moves required to pass to E is quadratic with respect to the number of crossings. These bounds apply both in S 2 and in ℝ2.

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.

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, ie., capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, UNKNOTTING PROBLEM is in NP. We also consider the problem, SPLITTING PROBLEM of determining whether two or more such polygons can be split, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. L. Tollefson.

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted (that is, whether it is capable of being continuously deformed without self-intersection so that it lies in a plane). We show that this problem, UNKNOTTING PROBLEM, is in NP. We also consider the problem, SPLITTING PROBLEM, of determining whether two or more such polygons can be split (that is, whether they are capable of being continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it), and show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE.