So here I am at FOCS in Philadelphia, the only place I've ever been that has plenty of good coffee shops, but they're all all closed on Sunday. My usual algorithm breaks down here—one block from every Starbucks is a Dunkin Donuts; all were packed this morning. I eventually found an Au Bon Pain (yes, one block from you know what). Grrr.
Anyway, as long as I'm here, I might as well pretend this is a computational geometry conference and blog about the talks. So here are four of the Sunday geometry talks:
- Mihai Pǎtraşcu presented his paper with Timothy Chan and Liam Roditty on geometric connectivity via subgraph connectivity. Subgraph connectivity means we want to maintain a graph under update operations that turn nodes on and off, while supporting queries of the form `Are s and t connected in the induced subgraph of on nodes?' In 2002 Timothy described reductions between geometric connectivity of axis-parallel boxes and subgraph connectivity. This paper extends Timothy's reduction to any family of geometric objects that supports linear-space sublinear-time range searching data structures (or a certain canonical type). In particular, for any class of semi-algebraic sets with constant description complexity, the linearization algorithm of Agarwal and Matousek gives an appropriate range searching structure, so the new results automatically give dynamic connectivity data structures with (barely!) sublinear update time. Careful but elementary balancing tricks improve the update time for abstract subgraph connectivity to roughly O(n^{2/3}); the best previous update time O(n^{0.94}) used fast matrix multiplication.
- Cora Boradaille presented a PTAS for Euclidean Steiner forest, which she developed with Phil Klein and Claire Mathieu. The new PTAS is an update of Arora's dynamic programming technique for Steiner tree. Arora builds a randomly shifted quadtree around the points. There is a near-optimal Steiner tree that crosses each cell boundary a bounded number of times. Moreover, if we place an evenly-spaced set of O(log n) points called portals on each cell boundary, there is a near-optimal solution that intersects cell boundaries only at portals. At this point, Arora's algorithm finds the best portal-respecting solution using dynamic programming. The table is indexed by a quadtree cell and a subset of portals on the boundary of that cell. This technique breaks down for the Steiner forest problem, in part because the dynamic programming tables explode. For Steiner tree we only need to check that each subsolution is connected, and that solutions glue together nicely at portals. For Steiner forest, however, we also need to keep track of which pairs of terminals are connected through each portal. Sotring all this information naively would require exponential space. The solution is to break each cell into a constant-sized grid, such that all terminals in the same grid cell connect to a common portal.
- The first geometry talk in the afternoon was by Esther Ezra, who presented her new proof that the union of n infinite 3D cylinders has near-quadratic combinatorial complexity. Her paper uses the same basic tools as Pankaj and Micha's "Pipes, Cigars, and Kreplach" paper—project the cylinders into the plane, build a cutting for the boundary lines of the projections, split the cylinders into canonical strips, classify the strips within each cutting cell as ‘wide’ or ‘narrow’, argue that most of the wide strips look like functions (and apply envelope sandwich arguments, and so on. The new analysis is considerably simpler than Pankaj and Micha's proof, and unlike the earlier proof, it applies to cylinders of arbitrarily different radii.
-
Anup Rao described his work on "spherical cubes" with Guy Kindler, Ryan O'Donnell, and Avi Widgerson. Here the problem is to find a shape that tiles d-dimensional space via some discrete lattice of transformations, such that the surface area of the tile is as small as possible. For the standard integer lattice, standard isoperimetric inequalities imply that any such shape has surface area Ω(√d). Anup described a randomized construction with surface area O(√d), improving the previous O(d) upper bound and matching the isoperimetric lower bound up to roughly a factor of 3. A key subproblem (pointed out by Deligne after the paper was submitted) is to find a convex body X in the unit hypercube [0,1]^d that maximizes the ratio volume/surface area. Once we have a body X with ratio O(√d), it can be transformed into a fundamental domain (or as they call it, a ‘spine’) for the unit d-dimensional torus with surface area O(√d), essentially by plopping down enough random copies of X to cover the unit hypercube.
Comments