VanderZee et al have solved an open problem in mesh generation from one of my earlier papers (with Sullivan and Üngör): is there a partition of a cube into tetrahedra, meeting triangle-to-triangle and edge-to-edge, with the property that ell the dihedral angles of every tetrahedron are acute? In our earlier work, we were only able to show the existence of acute triangulations of this type for infinite slabs, but the new paper shows that they do exist for cubes. The triangulation they find is well-behaved in other ways as well: the angles are bounded well away from right angles, and every tetrahedron contains its circumcenter.

This work raises the possibility that every polyhedron has an acute triangulation, but that remains an open problem still.

A flat torus is a surface topologically equivalent to a torus such that any point has a neighborhood that (in terms of the intrinsic metric of the surface) looks locally like a flat plane. Standard examples are the square and hexagonal torus in which the opposite edges of a square or hexagon are glued together. The square torus has a nice smooth embedding in four dimensions as the Cartesian product of two circles in perpendicular planes (the “Clifford torus”) but it seems difficult to embed in 3d: one can get a smooth cylinder by gluing one pair of edges but then to get the remaining two boundaries to meet each other it seems some crumpling is necessary. Perhaps surprisingly, with enough crumpling, it really can be embedded in 3d, within arbitrarily small volumes: this is the 2-dimensional case of the Nash–Kuiper theorem.

So if a 3d flat torus can't be smooth, how nice can it be? Maybe a polyhedron that, like the regular polyhedra and the Johnson solids, has only regular faces? This is the idea behind a question asked in 1997 by Nick Halloway: is it possible to form a polyhedral torus in which all faces are equilateral triangles and all vertices have degree six? It seems on the face of it that the answer should be no: if there are n vertices, there are 3n degrees of freedom for where they can be, matched by 3n distance constraints, leaving zero degrees of freedom, but any object that can actually be constructed in space has six degrees of freedom for its position and rotation. However, this is not a proof, because some of the distance constraints might be redundant and not reduce the degrees of freedom.

Undeterred, I tried playing with some physical equilateral triangles (from the geofix construction system), and built a structure that seems like it might work.



( Read more... )

I've been thinking again about minimum dilation stars (the subject of my paper arXiv:cs.CG/0412025 with my student Kevin Wortman).

Even for three points ABC, the problem of computing the “dilation center” O minimizing

max_{P,Q in {A,B,C}}(dist(P,O)+dist(Q,O))/dist(P,Q)

is interesting. ( Read more... )

ETA 7/28: Now X(3513) in ETC, where Peter Moses has supplied trilinear coordinates for it. Moses observed that it's not the only point formed as an intersection of three similar ellipses with these foci: X(3514), the point corresponding to the dilation center under an inversion through the circumcircle, with conjugate trilinears, also has this property. The dilation center is always interior to the given triangle, though, while Moses' point is exterior to it. The two new points are collinear with the incenter and circumcenter of the triangle.

At the open problem session today, Bojan Mohar plugged his Open Problem Garden, a wiki for unsolved problems in math. Unsurprisingly, it has a heavy bias towards graph theory, but there is some geometry there too.

The problem I described at the session was one I've already described here, so to make up for that here's one I asked Oswin Aichholzer earlier this week, after he gave a nice talk on finding geometric graphs in which each vertex has an adjacent wide angle. The prototypical example of a graph of this type is a pointed pseudotriangulation, a partition of the convex hull of a point set into polygons each having only three convex angles, such that each vertex has an incident concave angle. Every point set in general position has a pointed pseudotriangulation, as do some arbitrarily large subsets of grids:



However, some point sets in special position do not have pointed pseudotriangulations. If there is a point on an edge of the convex hull, it cannot have an incident angle greater than 180 degrees. And if all points lie on two lines and the crossing point of the two lines is included in the point set and interior to the convex hull (as in a quincunx) then that crossing point again cannot have a concave angle. Are those two types of point set the only ones with no pointed pseudotriangulation?

ETA 7/18: Oswin and Bettina Speckmann have found a few additional examples of point sets with no pointed pseudotriangulation. If they fit a more general pattern, I don't yet see what it is.

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.

Random observation that I don't recall seeing before: the edges from the sequence of convex hulls of a shelling of a point set forms a pointed pseudotriangulation: that is, it's a planar graph in which each interior face has three convex vertices and each vertex has one reflex angle.

But not every pointed pseudotriangulation can come from a shelling in this way: one can only have pseudotriangles with a single chain of reflex vertices, and there's some sort of acyclicity condition on the direction these chains can point. So the pseudotriangulations below do not come from shellings:

Since shellings are closely related to antimatroids, and antimatroids are related to certain kinds of greedy algorithms, perhaps this connection can lead to some algorithms for finding optimal pseudotriangulations...

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.

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.

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...

( Read more... )

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.

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.

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?

( Read more... )

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.

( Proof sketch )

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...

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.

( Cut for somewhat technical sequence of lemmas and proofs with no figures )

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.

( Cut for large image )

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.

( Read more... )

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

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.

( Non-crossing configurations and partial cube flip graphs )