Ernie's 3D Pancakes

Computational geometry at FOCS, part 2, plus true rumors

Here are a couple more computational geometry highlights from yesterday's FOCS schedule.

• Ankur Moitra and Tom Leighton solved the greedy embedding conjecture for 3-connected planar graphs, posed by Papadimitriou and Ratajczak in 2004. A path in the plane is distance-decreasing if the distance to one endpoint is monotonically decreasing as we walk along the path from the other endpoint. An embedding of a graph in the plane is greedy if every pair of nodes in the graph is connected by a distance-decreasing path. Papadimitriou and Ratajczak conjectured that every 3-connected planar graph has a greedy embedding. 3-connected planar graphs have tons of lovely geometric properties via theorems of Cauchy, Tutte, Steinitz, Koebe-Andreev-Thurston, and others, none of which proved useful in Moitra and Leighton's solution! Instead, they argue that any 3-connected planar graph (in fact, any circuit graph) has a spanning Christmas cactus, a subgraph in which every edge belongs to at most one cycle and deleting any vertex leaves at most two components, and then show how to greedily embed any Christmas cactus.

• Tasos Sidiropoulos described inapproximability resuls for metric embeddings into R^d, which he developed with Jiri Matousek. Given an n-point metric space M and a target dimension d, it is natural to ask for the minimum-distortion embedding of M into Euclidean d-space. Unfortunately, even for the case d=1, approximating the minimum distortion to small polynomial factors is NP-hard. Tasos and Jirka bootstrapped this known result to arbitrary dimensions, using a lovely product construction. If M is a bad example for embeddng into the line, then MxS is a bad example for embedding into R^d, where S is a sufficiently dense net on the (d-1)-sphere. Each copy of S must be embedded on an approximate sphere. A clever cohomology argument (hooray for Poincaré-Alexander duality!) then implies that these quasi-spheres are properly nested, which implies that the distortion is at least as bad as the distortion of M into the line. Thus result implies that random projection not only gives near-optimal worst-case distortion, but it also gives a nearly optimal approximation of the distortion for any metric space.

---

On our way to dinner last night, Mihai Patrascu asked me if the stories about my faculty job interview at MIT were true. Apparently, I impressed somebody (Mihai wouldn't say who) enough to become a cautionary example to MIT theory students. The story has become a little distorted over the last ten years, but yes, the essential details are accurate.

For any students entering the academic job market, who desperately want to avoid an offer from MIT, let me offer the following script, which proved wildly successful for me:

Gerry Sussman:

What's going to be the most important development in computer science in the next 20 years?

Yours truly:

I don't know, and neither does anyone else!

For extra added bonus points, make sure your tone of voice conveys just how incredibly stupid you think the question is.

I'm not crazy enough to think that was the only reason MIT didn't hire me—truthfully, I think they made the right decision—but it certainly didn't help. On the other hand, aside from a few added details about high school students and pornography, I'm not sure my answer would be much different today.

Computational geometry at FOCS

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.

Duality, duality, duality

Here are some slides from a talk I gave two weeks ago at the UIUC math colloquium (thanks, Nathan) and again earlier this week at TTI in Chicago (thanks, Benoît). We'll have a preprint soon, honest! Meanwhile, see how many different kinds of duality you can spot. Sadly, we couldn't work in the projective point-hyperplane duality that computational geometers usually use.

The background of the title slide is a shameless copy of Thorrun Arnadottir's very cool Blush radiator design. I really like her clock, too.

Hey! I can see my house from here!

Okay, I can sometimes see a greenish pixelated smudge in the neighborhood of my house, but still....

[Thx IlliniPundit]

Geometry and Algorithms

The newly-funded Center for Computational Intractability at Princeton is hosting Workshop on Geometry and Algorithms October 29–31, immediately after FOCS. The registration deadline is tomorrow. Here's a schedule.

Simultaneously, the annual Fall Workshop on Computational Geometry is being held at at Rensselaer Polytechnic October 31 and November 1. Here's a schedule.

I don't know which is more depressing—the partial overlap of the workshop dates, or the absolute lack of overlap in the workshop topics. I'm willing to bet that nobody will attend both workshops.

(I can't go to either workshop. I have a two-year-old. Halloween is sacred.)

Einspänner, bitte

The Institute for Discrete Mathematics and Geometry at the Technical University of Vienna is looking for a full professor in Discrete and Computational Geometry [pdf] (und auf deutsch [pdf]). Applications close December 30, 2008.

The applicant is expected to have outstanding academic credentials and an excellent track record of scientific accomplishments in the field of Discrete and Computational Geometry, focusing on a modern area of geometry related to methods of discrete mathematics, convexity, analysis and algorithmic theory as well as applications in science and technology. The successful candidate will be expected to make a significant contribution to the institute’s research output, to provide leadership for researchers and postgraduate students and to undertake an appropriate teaching load, in particular for students of mechanical and civil engineering. Special consideration will be given to the applicant’s ability and willingness to establish collaborations with institutions working in related fields of research and the demonstrated ability to attract external project funding.

No doubt this is related to Peter Gruber's imminent retirement.

Wahoolamazula! Yer Back!

After far too long an absence, Larry Marder is resurrecting his alternate-reality comic masterpiece, Beanworld!

The story is very simple, really. See, there are these beans that live on a small island floating on a thin lake over a sea of abstract Platonic forms called the Four Realities. Professer Garbanzo makes spears and other tools out of three of the four Realities; so far twinks have proven useless except to make art. Mr. Spook and the Chow Sol'jer Army use these to steal chow from the Hoi-Polloi, one-armed gamblers who live between the Bone Zone and Der Stinkle....

Oh, forget it. Just read the damn thing. You can see the latest Beanworld tale at Dark Horse Comics' Myspace page.

[Thanks, Boing²!]

---

See also 50 things that every great comics collection should have. Sadly, my superhero-deficient comics collection only scores 32/50.