price.mit.edu/blog

Math is hard

leave a comment

This week I got myself eaten by a math problem. Fortunately the problem is solved now, and I’ve escaped. Let me explain.

Two years ago, I was in Erik Demaine’s class about computational geometry, and heard about a problem that I wanted to solve. Suppose you have a convex polyhedron in ordinary 3-space. Then there is an intrinsic metric on the surface points of the polyhedron: the distance between two points is the length of the shortest path between them that runs along the surface. You can describe this metric to me without mentioning the embedding in 3-space, for instance by giving the shapes of a bunch of triangles and telling me which sides connect to which. The metric will certainly have these three properties:

  1. it’s homeomorphic to a 2-sphere: I can put the triangles all on a sphere preserving their interconnections, if I’m willing to stretch and bend them
  2. it’s a polyhedral metric: every point has a neighborhood with the same metric as a Euclidean disk (for most points) or cone (for the vertices)
  3. it’s locally convex: every circle of radius r has circumference at most 2πr

Now suppose you hand me a metric in the form of a bunch of triangles and notes on which edges to connect to which, and I confirm that they satisfy properties 1, 2, and 3. The great thing is that this is actually enough to guarantee that the triangles can be put together in 3-space to form some convex polyhedron, and this polyhedron is unique. (Here it’s crucial that I be allowed to bend the triangles, but without stretching — like paper.) Soviet mathematician A. D. Alexandrov proved this theorem in the 1940s. But Alexandrov’s proof doesn’t say how I can actually go and construct this embedding, so it opens up an algorithmic problem: given a metric satisfying properties 1, 2, and 3, how can we construct the unique convex polyhedron with this metric that Alexandrov’s theorem guarantees us?

Just the previous year, mathematicians Alexander Bobenko and Ivan Izmestiev had shown how to build the polyhedron by solving a rather involved differential equation. I figured it should be possible to get an explicit algorithm by discretizing their differential equation, and put a time bound on it by showing that the discrete steps don’t have to be too small. I cornered math problem-solver extraordinaire Daniel Kane, we sat down for a couple of hours with the Bobenko-Izmestiev paper, and he agreed—this shouldn’t be too hard.

Well, we were half right. Our approach worked, and we obtained an algorithm with an explicit time bound, a polynomial in the size of the input and its geometric ratios. Voilà:

Theorem. Given a convex polyhedral metric M homeomorphic to a sphere with n vertices, ratio S between the largest and smallest distance between vertices, and defect (discrete Gaussian curvature) between ε1 and 2π−ε8 at each vertex, an ε6-accurate ε9-convex embedding of M can be found in time

Õ(n915/2 S832 / (ε121 ε1445 ε8617) )

where ε = min(ε6/nS, ε9 ε12/nS6).

Now, that bound with its enormous exponents was great for getting people’s attention in talks. You don’t often see a time bound like that, and the reason is that to get that bound we had to pursue the problem and hammer it out piece by piece, assembling a diverse array of geometric lemmas, long past the point where sane people might have stopped. Daniel and I probably spent close to 100 hours meeting and working on the problem, some of it together with Erik, and I spent something like two or three times as long nailing all the details down in writing. The work became my master’s thesis, I presented it at the WADS conference this summer, and we submitted the paper to a journal. We breathed easy for a while.

Then we heard back from the reviewers. Turns out peer review is a good idea. One reviewer grabbed onto a particular subproblem that he apparently thought was more interesting than the whole rest of the paper. At each iteration we need to find an appropriate retriangulation of the surface. What we need is described by a well-understood concept, a “weighted Delaunay triangulation“. In the familiar Euclidean setting a Delaunay triangulation is equivalent to a “Voronoi diagram“, so we originally thought that some existing papers that described how to compute a Voronoi diagram on a polyhedral surface were enough to give us the weighted Delaunay triangulation we needed.

This reviewer demanded we give more attention to the issue, and he was right—the problem was harder than we realized. On a polyhedral surface things are more complicated than in the plane; for one thing, there can be infinitely many straight lines between two points, and to make a Delaunay triangulation you need to use the right ones. But in two marathon sessions this week and 2000 words of writing, Daniel and I worked out how to get an unweighted Delaunay triangulation from a Voronoi diagram, and then how to adjust the triangulation to handle weights. So the reviewer was right to think the problem more interesting than we had treated it, and now we’ve solved it. Since our new algorithm for Delaunay triangulation is straightforward and is known to run in a practical amount of time, it may prove to be the most reusable part of the paper.

Anyone interested can read more in the paper (pdf). The new Delaunay triangulation algorithm is in the last section.

So that was my vacation. How was yours?

Written by Greg Price

January 4th, 2010 at 1:32 am

Posted in Uncategorized

Tagged with , ,

Leave a Reply