[PAST EVENT] Geometry and Topology Meet Graph Algorithms

February 1, 2016
8am - 9am
McGlothlin-Street Hall, Room 020
251 Jamestown Rd
Williamsburg, VA 23185Map this location
8:00 AM, McGlothlin-Street Hall 020

Kyle Fox, Duke University

Title: Geometry and Topology Meet Graph Algorithms


In this talk, I will discuss recent work in the areas of computational geometry, computational topology, and graph algorithms. While these topics may appear somewhat disparate, it turns out that problems from each area may best be tackled with a thorough understanding of both areas.

I will describe in detail two recent pieces of work. First, I will describe a near-linear time algorithm for approximating two well-known distance measures that arise in trajectory analysis, emphasizing my use of graph algorithm techniques to bypass natural running time barriers. Second, I will describe an approximation algorithm for finding the cheapest way to partition a planar graph into two pieces of equal size. This latter algorithm relies on the topology of the graph's embedding in the plane to work efficiently. A combined understanding of geometry, topology, and graph algorithms makes it possible to achieve faster running times and good approximations in both of these examples.


Kyle Fox is currently a postdoctoral associate at Duke University. He obtained his Ph.D. from the University of Illinois at Urbana-Champaign in 2013, and then completed a postdoctoral fellowship at the Institute for Computational and Experimental Research in Mathematics at Brown University before coming to Duke. His research interests lie in various areas of theoretical computer science, including computational geometry and topology and combinatorial optimization. He was a recipient of the Department of Energy Office of Science Graduate Fellowship and a winner of the C. W. Gear Outstanding Graduate Student award while at the University of Illinois.