SoCG 2006: Overlays of Minimization Diagrams

Tuesday was the day of the banquet. The "banquet" was a jeep tour of Sedona, ending at Sedona airport (on a hill. I repeat: Sedona airport is on a hill). The overlook near the airport is a great place to see the sunset (in principle, but more on that later), and looks out over the entire town.

The jeeps are open-air seven-seaters, the kind of "SUV" that was really designed for offroading, Trust me when I tell you that none of the wimpy SUVs you see on the road would have survived the bone-rattling trip we took. As I said to someone later on, it was like going on a roller coaster over a discontinous function.

The usual tourist patter aside, it was a great ride. 5 of the jeeps took a more "rugged" ride, and although all my bones were aching the next day, it was worth it ! This ranks up there with the S0CG 2004 Manhattan cruise-with-open-bar (yes, geometers do have too much fun).

And now, back to business. The featured paper of the day is 'Overlays of Minimization Diagrams' by Vladlen Koltun and Micha Sharir.

The lower envelope of an arrangement of entities in R^d (the set of entities you hit first as you move upwards from z = -infinity) is a very important structure in geometry. Many optimization problems can be expressed as searches over a suitably defined lower (or upper) envelope, or combinations thereof. A minimization diagram is what you get when you project the lower envelope onto the underlying domain one dimension lower. The best example of this is a Voronoi diagram of points, which as we all know is the projection of the lower envelope of an arrangement of suitably defined cones.

What do you get if you take two such minimization diagrams and put them on each other ? This overlay, which itself is another subdivision of space, is also useful in geometric optimization. The canonical example here is the computation of a minimum width annulus of a set of points. I'd like to find a center, and two concentric circles of radius r and R, so that all the points in my input are enclosed between the two circles, and R-r is as small as possible.

This problem is a robust version of circle fitting, or checking how close points are to a circular shape. It's not hard to see that what you need is a large empty circle, and a small enclosing ball, both centered at the same point. Any vertex of a Voronoi diagram gives you a large empty circle (in fact, a maximal empty circle). If you computed a "farthest-point" Voronoi diagram, i.e a minimization diagram from the upper envelope, you'd get candidates for the smallest enclosing ball. It turns out that the center of the optimal minimum width annulus must be a vertex of the overlay of these two minimization diagrams.

As with many geometry problems, we quickly go from searching to counting, from "find the optimal x satisfying property P" to "Enumerate all the x that can satisfy property P". The question in this case is: What is the complexity of the overlay of two minimization diagrams ?

Of course, a more basic question is: what is the complexity of one minimization diagram ? For the case of hyperplane arrangements, the answer follows from the famous Upper Bound Theorem of McMullen from 1970:

The complexity of the lower envelope of a collection of n hyperplanes in d dimensions is n^⌊d/2⌋.

Given this, an easy bound on the overlay of two such diagrams would be n^{2 * ⌊d/2⌋}, merely by observing that every intersection of two features creates a new feature. The main result of this paper is that the correct answer is much smaller:

The complexity of the overlay of two minimization diagrams for collections of n hyperplanes in d dimensions is n^⌈d/2⌉.

Note the flip from floor to ceiling. This creates some unusual effects; the complexity of the overlay of two minimization diagrams in odd dimensions has the same complexity as that of one such diagram; in even dimensions, the difference is one (remember that the minimization diagram inhabits one fewer dimension than the arrangement of hyperplanes defining it).

The key lemma that establishes this fact is very simple; indeed the authors express surprise that this lemma hasn't been observed before. It involves a "reversal of operators": namely, that the overlay of minimization diagrams can be expressed as a minimization of overlays.

More formally,

The overlay of two minimization diagrams of n d-variate functions is isomorphic to a subset of the minimization diagram of 2n d+1-variate functions.

The result above extends to 2 <= m <= d. Similar results also hold for arrangements of simplices, or of constant-degree algebraic functions. They all follow almost directly from the above lemma.

Categories:

• research
• socg06