Computer Science Events
This calendar presented by
Computer Science
[PAST EVENT] Geometry and Topology Meet Graph Algorithms
February 1, 2016
8am - 9am
8:00 AM, McGlothlin-Street Hall 020
Kyle Fox, Duke University
Title: Geometry and Topology Meet Graph Algorithms
Abstract:
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.
Bio:
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.
Kyle Fox, Duke University
Title: Geometry and Topology Meet Graph Algorithms
Abstract:
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.
Bio:
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.