ContactAs of January 2011, I am working as a Software Engineer at Google Pittsburgh.
Formerly part of Computer Science Department |
Hiking at Ohiopyle State Park with Emma the dog |
I work in Algorithm Design and Computational Geometry. My main research focus has been on Meshing Algorithms. The goal of Meshing is to discretize a geometric domain into simple pieces such as triangles or tetrahedra. In particular, one seeks guarantees about the element-size, element-shape, output-size (number of elements) in the mesh, as well as the usual algorithmic guarantees on time and space complexity.
Currently, I spend most of my time on meshing algorithms with efficient worst-case asymptotic runtimes. Many meshing algorithms have $O(n^2)$ or worse runtime on bad inputs. We have shown that is possible and practical to reduce this to roughly $O(n\log n)$ using simple Sparse Refinement techniques to modify existing algorithms.
We present a new meshing algorithm for the plane, Overlay Stitch
Meshing (OSM), that accepts as input an arbitrary Planar Straight Line
Graph and produces a triangulation with all angles smaller than 170
degrees. The output triangulation has size that is competitive with
any optimal size mesh having bounded largest angle. The competitive
ratio is O(log(L/s)) where L and s are respectively the largest and
smallest features in the input. OSM runs in O(n log(L/s) + m)
time/work where n is the input size and m is the output size. The
algorithm first uses Sparse Voronoi Refinement to compute a quality
mesh of the input points alone. This triangulation is then combined
with the input edges to give the final mesh.
Practical, runtime-efficient, size-guaranteed meshing algorithm produces a quality
radius-edge mesh in three dimensions or any fixed constant dimension.
Runtime is asymptotically optimal for fixed-word size inputs; greatly
improved runtime bounds versus existing similar algorithms.
The first subquadratic runtime bounds for three dimensions or higher.
Later work shows how to exploit the natural parallelism of this
algorithm in a PRAM with runtime and work nearly optimal;
vastly improving on existing bounds for parallel meshing.
Tech-Report Long Version:
CMU-CS-06-132
Data structure for storing and manipulating the topological
structure (connectivity and neighborhoods) of a broad algebraic class of
complexes, including a non-manifold generalization of cell complexes.
A method for performing complex fluid-flow simulations. We use a
free Lagrangian method with a high-order Bezier basis and perform
dynamic mesh updates (refinement, coarsening, and connectivity). In
later work, we extend the method to handle Elastic Membranes using a
new variant of Peskin's model.
Tech-Report Long Version:
CMU-CS-03-166