I've been visiting Dublin, Ireland (my first time here) for the Fifth William Rowan Hamilton Geometry and Topology Workshop at the Hamilton Mathematics Institute of Trinity College, where I spoke about hyperconvex metric spaces, finding optimal stars, orthogonal convex hulls, and embedding into the Manhattan plane.

It was a good conference, but a bit like stepping into a parallel world where everyone's evil twin does low-dimensional topology and geometric group theory: the workshop theme had the phrase "Computational Geometry" in it, but it's an Other Computational Geometry that really mostly means low-dimensional topology and geometric group theory; there's an Other David Epstein (spelled wrong) who does etc and was here last year; and there's an Other Kevin Wortman (not spelled wrong) who does etc and wasn't here, but whose name caused some confusion when I referred to the work of my former student Kevin Wortman. Still, my interests and those of the Other Computational Geometers have enough overlap that I think we all got something useful out of the experience.

I'm not going to recount all of the talks (especially because I didn't understand them all) but here are a few that caught my attention.

( Read more... )

The slides from Elena Mumford's talk at SODA on our paper, “Self-overlapping curves revisited” (arXiv:0806.1724) are now online, including a few she skipped in the presentation.

Several people asked us the same two questions afterwards. First: how did you make such beautiful drawings? I can phrase it like that without fear of immodesty because Elena made the drawings, by hand with colored pencils, and then scanned them. Her colleagues at Eindhoven told me she also had some nice large 3d models made out of semitransparent plastic that would have made an interesting addition to the talk, but unfortunately she didn't bring them.

The second question we were asked is what applications we had in mind. The short answer is that this is a theory paper that isn't trying to be applied, but after the talk Yusu Wang discussed with Elena an application involving finding similarities between pairs of curves (one of Yusu's two SODA papers involved using Fréchet distance for this sort of comparison). Unfortunately I'm not sure of the details of the application. More generally, beyond the specific results in the paper itself, we think that one of its important contributions is the definition of a generalized terrain as a surface such that every point has a neighborhood within which the surface is a terrain. There should be many more problems in which these surfaces can be applied, and we tried to convey that in the talk slides by the images of real-world spiral ramps forming surfaces of this type that we found on Flickr. Sadly, we didn't end up using another photo we found, of the generalized terrain formed by a giant helicoid potato chip (or as Elena would call it a crisp), perhaps because it didn't have the proper salt-and-vinegar flavoring.

I'm visiting Eindhoven in the Netherlands this week, as the outside examiner for Elena Mumford's thesis defense which happened today (that is, Monday, though I guess it's officially Tuesday by the time I'm posting this) and which she passed with flying colors. Today I also heard the good news that Elena's paper (with me), Self-Overlapping Curves Revisited, which formed one of the chapters of her thesis, was accepted to SODA. Double congratulations, Dr. Mumford!

Two papers my coauthors and I recently uploaded to the arXiv:

( Succinct Greedy Graph Drawing in the Hyperbolic Plane )

( Self-Overlapping Curves Revisited )

At WADS last summer Jeff Erickson gave a nice talk about Rips complexes, which I also posted about here a while back, and last month Jeff and his co-authors posted their preprint to the arxiv, at which point I dumped it in my folder of recent arxiv preprints that I should really read and try to understand someday. But then it was the holidays and I got busy with other stuff and I didn't get around to looking at it until now, when Jeff and his student Erin Chambers (another of the preprint co-authors) are visiting and I could just ask them to tell me what's in it rather than having to take the trouble to read it myself.

( Read more... )

Low Dimensional Topology and Sketches of Topology. Lots of math in the former. Lots of pretty mathy illustrations in the latter.

Based in part on Jeff Erickson's nice invited talk on algorithms for finding small cycles in topological spaces at WADS, I just added a brief survey on Vietoris–Rips complexes to Wikipedia.

I'm a little worried that one point I included may violate Wikipedia's prohibition on original research, though: the Vietoris–Rips complex of any metric space X turns out to always equal the Čech complex of some set of balls in some larger space into which X can be embedded.

Specifically, if X is embedded in any injective metric space Y, then the Vietoris–Rips complex for distance δ in X is the same as the Čech complex for the balls of radius δ/2 centered at the points of X in Y: the Rips complex includes a simplex for any finite set of balls that intersect pairwise, the Čech complex includes a simplex for any finite set of balls with a common intersection, and an injective metric space is defined by the property that any set of balls that intersect pairwise has a common intersection. Since any metric space can be embedded in an injective space via the tight span, the result follows.

This seems obvious enough (and important enough) that I'd include it in a survey or research paper on a related subject without attempting to assign or take credit for it, but Wikipedia has different standards: everything must have a source. So, can anyone help me find a published paper that includes something resembling this statement? I suppose in the worst case that this blog post might suffice, but it's not a very good source by Wikipedian standards...

ETA: Carlsson says he doesn't know more than what's in his new paper (which mentions that the two complexes are the same for L_∞ spaces), and he should know. And Jeff has put his talk slides up.

I have another new paper up on arXiv, titled "Manhattan orbifolds". It's about 2-dimensional manifolds with hyperconvex metrics, which is to say that they have properties similar to L_∞ metrics in Rⁿ.

The original idea was that these things might be useful in designing approximation algorithms for the hyperbolic plane, related to my squarepants paper. But, though the paper does describe a hyperconvex approximation to the hyperbolic plane, I haven't yet found any approximation algorithms based on it, and there isn't really any algorithmic content in the paper. Instead it turned into something about distances in graphs (squaregraphs, which are a type of partial cube, and certain other related graphs).

Via Sariel: The Story of Lemma 5.6. Keenan Crane attempts to convey a computational topology proof through talk slides in a children's-picturebook style. My impression: it works very well for helping me to remember what objects all those similar Greek letters are standing for, less well at making clear what are the assumptions of the lemma and what is the consequence that's supposed to follow from those assumptions.

Lego webcomic for topology nerds. Syndicated here as irregular_comic. Time to augment my flist...

It turns out there's a very simple characterization of xyz graphs: if a graph G is embedded on a surface, then that embedding can be represented as an xyz graph, with the surface represented via the flat polygons of the xyz graph, if and only if: (1) every face of the embedding is a disk without repeated vertices, (2) if any two faces intersect, they do so in an edge, and (3) the faces can be 3-colored.

For instance, the following three tori (drawn as rectangles with periodic boundary conditions) all form xyz graphs. The left one is the nine-hexagon torus we've already seen before, center is another twelve-hexagon torus, and right is a torus embedding of the four-dimensional cube-connected-cycles network (and also a GEM for K_4,4).



( Read more... )

For lack of a more creative name, I've decided to call the graphs I discussed a couple days ago, formed from point sets intersecting any axis-parallel line in zero or two points, xyz graphs. The ones that fit in a 2×n×n grid are just the prisms over even polygons. Up to graph isomorphism there are only three that fit in a 3×3×3 grid:



Left to right, the flat polygons of these graphs form a projective plane closely related to the one in the previous posting, a planar graph with nine faces, and a torus with nine hexagonal faces. The enumeration of such graphs within a 4×4×4 grid should be well within computational reach since each such graph can be determined by the presence or absence of vertices within a 3×3×3 subgrid.

( Orientability equals bipartiteness )

( Connectivity )

( Arbitrary genus )

( High genus in small cubes )

Suppose we have a point set S in 3d such that any line parallel to a coordinate axis intersects S in either zero or two points. If we draw a graph by connecting pairs of points on the same line, we get a 3-regular graph, such as the one below.



What other properties must such a graph have? For instance, they can't contain a K_2,3 subgraph, a triangle, or a pentagon. After thinking some more about the inverse permutohedron example I posted the other day, I started to wonder, do such graphs always form partial cubes?

( Read more... )

Now that I'm back from SODA, I guess it's appropriate for me to post a recap of some of the more memorable parts of it for me.

( Eventfulness )

( Bloggers )

( Topology )

( Geometry )