We present an algorithm for surface reconstruction from a point cloud. It runs in O ( n log n ) time, where n is the number of sample points, and this is optimal in the pointer machine model. The only existing O ( n log n )-time algorithm is due to Funke and Ramos, and it uses some sophisticated data structures. The key task is to extract a locally uniform subsample from the input points. Our algorithm is much simpler and it is based on a variant of the standard octree. We built a prototype that runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the sample points absent from the subsample via edge flips. In our experiments with some nonuniform samples, the subsample extraction step is fast and effective, and the prototype gives a 51% to 68% speedup over using Cocone alone. The prototype also runs faster on locally uniform samples.

Let be a planar subdivision with n vertices. Each face of has a weight from [1, ρ] ∪ {∞}. A path inside a face has cost equal to the product of its length and the face weight. In general, the cost of a path is the sum of the subpath costs in the faces intersected by the path. For any ε ∊ (0, 1), we present a fully polynomial-time approximation scheme that finds a (1 + ε)-approximate shortest path between two given points in in time, where k is the smallest integer such that the sum of the k smallest angles in is at least π. Therefore, our running time can be as small as if there are O(1) small angles and it is in the worst case. Our algorithm relies on a new triangulation refinement method, which produces a triangulation of size O(n + k2) such that no triangle has two angles less than min{π/(2k), π/12}.

We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L1 and L∞ shortest paths on a polyhedral surface in O(n2 log4 n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)-approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O[EQUATION]. This is the first efficient PTAS for such a general setting of terrain navigation.

We present an approximation algorithm for the shortest descending path problem. Given a source $s$ and a destination $t$ on a terrain, a shortest descending path from $s$ to $t$ is a path of minimum Euclidean length on the terrain subject to the constraint that the height decreases monotonically as we traverse that path from $s$ to $t$. Given any $\varepsilon \in (0,1)$, our algorithm returns in $O(n^4\log (n/\varepsilon))$ time a descending path of length at most $1+\varepsilon$ times the optimum. This is the first algorithm whose running time is polynomial in $n$ and $\log(1/\varepsilon)$ and independent of the terrain geometry.

We present an approximate algorithm for the shortest descending path (SDP) problem. Given a source s and a destination t in a polygonal terrain T, an SDP from s to t is a path in T of minimum Euclidean length subject to the constraint that the height decreases monotonically as we traverse that path from s to t. Given any ε ∊ (0, 1), our algorithm returns in O(n4 log(n/ε)) time a descending path of length at most 1 + ε times the optimum. This is the first algorithm whose running time is polynomial in n and log(1/ε) and independent of the terrain geometry.

We present an algorithm to reconstruct a surface from a dense sample. Given n sample points, it runs in O(n log n) time, which is optimal in the pointer machine model. The only existing O(n log n)-time algorithm due to Funke and Ramos uses some sophisticated data structures for the key task of extracting a locally uniform subsample. Our algorithm is based on a variant of the standard octree, and it is much simpler. We built a prototype, which runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the samples points absent from the subsample via edge flips. The subsample extraction step is very fast and effective. In our experiments with some non-uniform samples, our prototype gives a 51% to 68% speedup from using Cocone alone. Even for locally uniform samples, our prototype is usually much faster.

We study edge flips in a surface mesh and the maintenance of a deforming surface mesh. If the vertices are dense with respect to the local feature size and the triangles have angles at least a constant, we can flip edges in linear time such that all triangles have almost empty diametric balls. For a planar triangulation with a constant angle lower bound, we can flip it to the Delaunay triangulation in linear time. We combine edge flips and vertex nsertions and deletions in an algorithm to maintain a deforming surface mesh, specified only by a dense sample of n points that move with the surface. Under a reasonable motion model, we can enforce bounded aspect ratios and a small approximation error throughout the deformation. The update takes O(n) time at each time step. Our surface mesh maintenance algorithm also gives a good performance in experiments.