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 Advisor: Gary Miller Home: (412) 983-2169 Email: toddphillips at gmail dot com

Hiking at Ohiopyle State Park with Emma the dog

Teaching

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

• 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