# Todd E. Phillips

### Contact

As of January 2011, I am working as a Software Engineer at Google Pittsburgh.

Formerly part of Computer Science Department
at Carnegie Mellon University
Home: (412) 983-2169
Email: toddphillips at gmail dot com

Hiking at Ohiopyle State Park with Emma the dog

### Teaching

Fall Semester 2006, I was a TA for 15-251 Great Theoretical Ideas in Computer Science
Spring Semester 2005, I was a TA for 15-451 Algorithms

### Research Interests

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.

### Research / Publications

Sangria project.
TUMBLE Software package.
Sparse Voronoi Refinement Meshing Code.
• Size Competitive Meshing without Large Angles. G. Miller, T. Phillips, and D. Sheehy. ICALP 2007.

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.

• Sparse Voronoi Refinement. B. Hudson, G. Miller and T. Phillips. 15th International Meshing Roundtable, 2006. (bib).
Sparse Parallel Delaunay Mesh Refinement. B. Hudson, G. Miller and T. Phillips. Symposium on Parallelism in Algorithms and Architectures, 2007. (To Appear).

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

• Representing Topological Structures Using Cell-Chains. D. Cardoze, G. Miller, and T. Phillips. Geometric Modelling and Processing 2006. (bib).

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 Bezier-Based Approach to Unstructured Moving Meshes. D. Cardoze, A. Cunha, G. Miller, T. Phillips, N. Walkington. 20th ACM Symposium on Computational Geometry. 2004. (bib).
A Bezier-Based Moving Mesh Framework for Simulation with Elastic Membranes. D. Cardoze, G. Miller, M. Olah, and T. Phillips. 13th International Meshing Roundtable. 2004. (bib).

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

Some Mesh Pictures from a Project on Multiscale Astrophysics:
A really big mesh of the Steelers logo: