13 May 2012 @ 11:38 pm
A paper uploaded to the arXiv this evening by Anna Lubiw and Vinayak Pathak just caught my attention. I think the title speaks for itself (always a good thing for a title to do): Flip Distance Between Two Triangulations of a Point-Set is NP-complete. The proof doesn't look very hard, once you see it: a standard gadget-based reduction to a variation of the problem for polygons with holes, together with another reduction from polygons to point sets that consists of protecting the polygon edges with layers of triangles that would be too expensive to flip through.

Although it's a big step forward, the paper still doesn't resolve the question of how hard it is to compute flip distance between triangulations of a convex polygon. This remains as a big open problem, one of a small number of natural problems neither known to be polynomial time nor known to be NP-hard.

15 March 2011 @ 03:12 pm

I'm very interested in a recently updated arXiv paper by Bodini, Fernique, Rao, and Remila, "Distances on Rhombus Tilings", arXiv:0911.2804. It finds yet another example (like the one in my "happy ending" paper) of a family of flip graphs that are automatically partial cubes.

)

23 February 2011 @ 07:49 pm
What I'm reading this evening: "The Pachner graph and the simpliﬁcation of 3-sphere triangulations", by Benjamin Burton, arXiv:1011.4169. He posted it last November, but revised it again recently and somehow the revision caught my attention after the original posting didn't. It's also one of the papers included in the recently posted list of SoCG acceptances.

The basic problem it deals with is trying to tell different three-dimensional spaces apart from each other, and in particular how to distinguish the three-sphere (a space that can be formed from the familiar Euclidean space by adding a single "point at infinity") from other topological spaces.

The spaces given as input to the problem are described as a set of tetrahedra together with a pattern for gluing their faces together, and one way to solve this in practice is to perform flips (local operations that change the set of tetrahedra without changing the topological type of the input) until reaching a simplified and recognizable gluing pattern. It's known that repeated flipping from any topological 3-sphere can eventually reach a canonical triangulation that consists a single tetrahedron glued to itself, but it's not always possible to do this using flips that decrease the number of tetrahedra — sometimes one has to increase the number of tetrahedra before decreasing it again.

What Burton does is to implement and test this algorithm on approximately 31 million different 9-tetrahedron complexes. He shows that, in these cases, all of the local minima in the flip graph are shallow: one only ever needs to increase the number of tetrahedra by two to find a path to the global minimum. This is in strong contrast to proven superexponential upper bounds on the number of additional tetrahedra.

Burton's results are consistent with past experience with programs like SnapPea, suggesting that these problems are a lot easier in practice than our current theory tells us, and they're enough for him to make some conjectures that, if true, would imply that 3-sphere recognition could be solved in polynomial time.

07 June 2007 @ 04:33 pm
Suresh has been blogging up a storm about SoCG, while instead I played hooky this afternoon to visit Seokguram and Bulguksa. (Sadly, the light was grey and flat, so don't expect photos, but both were definitely worth seeing in person.) Except for the difficulty of getting here, this has been a great location for a conference: a high quality hotel with reasonable rates, nearby restaurants with great food at low prices (my favorite so far: Bersayu, an excellent sit-on-the-floor barbecue dinner for about \$6), decent espresso nearby albeit at high prices, and an impressive cultural heritage.

Anyway, here at least are the talk slides from my two talks yesterday: Guard placement for wireless localization (with Nodari Sitchinava and Mike Goodrich) and Happy endings for flip graphs.

06 February 2007 @ 09:57 pm
Happy Endings for Flip Graphs was accepted to SoCG 2007, as was another paper of mine: Guard Placement For Wireless Localization, with Mike Goodrich and Mike's student Nodari Sitchinava. So I guess that means I'm going to Korea...

ETA: The full acceptance list, Suresh's minimalist remarks, and Sariel's hideous frozen cat atrocity.

16 October 2006 @ 10:46 pm
I've written up my results on flip graphs, partial cubes, and the happy ending theorem, and uploaded it to arxiv: Happy endings for flip graphs.

15 October 2006 @ 11:56 pm
The triangulations of a regular n-gon, embedded in the plane with a marked edge, can be placed in one-to-one correspondence with binary trees having n-1 leaves: each tree is essentially just the planar dual graph to a triangulation, rooted at the marked edge. But the markings needed for this correspondence mess up the symmetry of the n-gon.

This issue of symmetry has some relevance to geometric constructions of the associahedron, the polytope whose skeleton is the flip graph of triangulations or the rotation graph of binary trees. One would like a realization of the associahedron as a geometric object with at least as much symmetry as the regular polygon being triangulated, but the general constructions I've seen for embedding associahedra as polytopes don't do that, and I don't know whether it's possible in general. I can see how to do it in two and three dimensions, but after that my ability to visualize what's happening runs into trouble...

)

13 October 2006 @ 10:27 am
This is the flip graph of a convex hexagon. It is planar, but I wanted to communicate (1) that it is the skeleton of a polyhedron (the associahedron), and (2) that the top and bottom vertices are at distance four from each other. I think the drawing below communicates that better than a planar drawing would have. It's a bit distorted from the projection of a symmetric convex polyhedron, I think, mainly because I wanted to avoid having the middle row of triangulations overlap each other.

08 October 2006 @ 06:33 pm
Someone asked me where I was going with flip graphs of grids, and I didn't know at the time. But I got a hint the other night, and now I think I can prove it: a point set has a partial cube flip graph if and only if it has no empty pentagon. I think I'll wait until writing it up more carefully to give details of the proof, but the significance of this (beyond being pretty) is that it means we can compute the flip distances for these point sets easily, compared to e.g. convex polygons where computation of flip distances is a famous open problem (see e.g. Sleator Thurston and Tarjan 1986). Also I think the proof is easier in this level of generality than it is for grids.

To keep this from being content-free, here's an example showing that point sets without empty pentagons can be complicated. One more level of inscribed pentagons and there would be an empty one... I also have several infinite families beyond the one we already knew, convex subsets of a projective transformation of a grid.

06 October 2006 @ 01:49 am
I know it's ridiculously late, but when I get ideas late at night I tend not to be able to sleep until I write them down, and here's as good a place as any for that.

Anyway, you remember (or probably you don't, but I do) that classification of dilation-free planar graphs I did a while back, that's now been incorporated into a paper with Dujmović, Suderman, and Wood?

)

So anyway, there's a much easier way to describe the same family of point sets, closely related to the famous happy ending problem: these are exactly the point sets that have no strictly-convex empty quadrilateral. They're also the point sets with exactly one triangulation.

)

It's known by now that every sufficiently large point set in general position has a strictly-convex empty hexagon but of course these point sets aren't in general position...

23 September 2006 @ 08:10 pm

The labeling scheme I described for the 3x3 grid appears to generalize to show that any grid has a flip graph that embeds isometrically into a hypercube.

)

22 September 2006 @ 04:35 pm
Here is the flip graph of 3x3 triangulations again, with the triangulations grouped according to their set of length-sqrt(2) edges. The number of edges shown between each pair of groups indicates the number of pairs of triangulations that can be flipped from one group to the other. Despite not showing the detailed connections as well, I think this kind of clustered graph drawing makes the overall structure of the flip graph much clearer.

)

22 September 2006 @ 12:25 am
Following up my recent post on triangulations of points on two lines, I spent some time on the plane home today thinking about the next simplest case: a 3x3 grid. It turns out that the triangulations of these 9 points can be labeled by 12-dimensional bitvectors in such a way as to make them a partial cube.

)

This still seems a small enough example that I'm not willing to guess whether the partial cube property generalizes to larger grids.

18 September 2006 @ 09:57 pm

I'm in Karlsruhe for Graph Drawing 2006. The first day had many interesting talks; my own (in the session on tree drawing) seemed to go well, and I've put the slides online here.

)