SCS Faculty Candidate

NSF Mathematical Sciences Postdoctoral Fellow
Department of Computer Science
Columbia University
Optimizing Algorithms at the Level of Geometry
Tuesday, April 8, 2014 - 1:00pm
Newell-Simon Hall

The world around us is comprised of three-dimensional geometry: from the cars we drive and the clothes we wear, to the food we eat and the organs in our bodies. To a large extent, our ability to make sense of the world is therefore limited by our capacity to design, process, and analyze geometric data. My work explores how different choices of geometric representation can profoundly influence the effectiveness of computational algorithms.

The guiding principle is to view computation through the lens of smooth differential geometry, leveraging a diverse range of perspectives from modern mathematics. In a variety of problems, this approach has proven quite fruitful: difficult nonlinear PDEs are replaced with linear ODEs, difficult hyperbolic problems are transformed into simpler elliptic ones, and difficult nonconvex optimization problems are replaced by simple convex problems that easily admit globally optimal solutions. Each of these transfor-mations has produced valuable practical outcomes, making common geometry processing tasks orders of magnitude faster, providing provable guarantees on the quality of the output, and ex-tending algorithms to a wider class of inputs.

In this talk I will discuss a new method for computing fast distance transforms, tools for optimal direction field design, and a new framework for surface processing that naturally preserves geometric fidelity. These tools address the growing need for geometric understanding not only in traditional areas like science and engineering, but also in rapidly developing consumer domains like 3D printing and augmented reality.


Keenan Crane is an NSF Mathematical Sciences Postdoctoral Fellow at Columbia University. He received a B.S. from the University of Illinois at Urbana-Champaign in 2006, and a Ph.D. from the California Institute of Technology in 2013. His work draws on insights from differential geometry and computer science to develop fast numerical algorithms for working with real-world geometric data; this work has been used in production at companies such as DreamWorks and Digital Domain, and has been covered by popular media including National Public Radio and Scientific American. He is the recipient of a Google Ph.D. Fellowship and an Everhart Distinguished Lecturer Award.

For More Information, Please Contact: