## Monday, July 24, 2006

### Where duality helps

If you do geometry (or approximation algorithms, for that matter) long enough, it becomes second nature to flip between primal and dual space. Points become hyperplanes, convex hulls become envelopes, and so on.

Here's a question that has been puzzling me: What is a good example of a problem where flipping between primal and dual (or even just going from one to the other) is the key to its solution ? Now obviously, there are NP-hard problems that admit a primal-dual solution, where by definition we need the dual space. I don't mean these kinds of problems.

I'm merely wondering if there is a relatively simple problem with a relatively simple solution that would be hard to explain without duality. The easiest that comes to mind is how the complexity of the convex hull in 3D is linear (because the complexity of the lower envelope in 3D is linear). Another potential example is the rotating calipers method for finding diameter/width etc: it can be much easier to see what's going on in the dual space.

Categories:

1. It is hard to find such examples because naturally duality when used correctly is such a small fraction of the argument and one can not see how critical it is without it. A striking example is Overmars and J. van Leeuwen work on the dynamic maintenance of cover hull in 2d, and the maintenance of the lower/upper envelope of lines in the plane. Clearly, by duality the two problems are identical. However, the authors (smart people indeed) did not observe it, and the paper is twice longer than it should be solving the two problems separately. Note, that this is a very early paper in CG so their failure to observe the duality is not too shocking.

Posted by Anonymous

2. the book chapter by dobkin and souvaine (in a robotics text i believe) has a primal-dual section and contains many such examples where duality is the key.

Posted by Anonymous

3. Dey's k-set upper bound? Switches back and forth a couple times if I remember correctly.

4. "The easiest that comes to mind is how the complexity of the convex hull in 3D is linear (because the complexity of the lower envelope in 3D is linear)."

Huh? Euler's formula is self-dual!

Halfspace range searching data structures are a good example. Small structures with near-linear query times tend to be described in the primal setting (data=points, query=halfspace); whereas, large structures with small query times tend to be described in the equivalent dual setting (data=halfspaces, query=point). At a deeper level, though, those 'primal' partition trees depend on 'dual' cuttings for their construction, so the primal/dual separation is not quite sp clean. And there are continuous tradeoffs between these two extremes, where the data structure uses different geometric interpretations at different levels.

Well, actually, the data structure does no such thing. In fact, it doesn't use any geometric interpretations at all.

Duality is only the most common example of the more general idea that the same underlying linear/polynomial algebra can have multiple geometric interpretations. Thus, Voronoi diagrams are really convex hulls one dimension higher; lines in space are really moving points in the plane; linear programs are really equivalent to their (Gale) duals. Do those three real numbers "really" represent a point in space, a plane in space, a circle in the plane, a conic curve passing through two fixed points in the plane, the position and orientation of a planar robot, a line rotating in the plane at constant speed, a point moving on the line with constant acceleration, or a Mobius transformation of the complex plane? All of the above, and none of the above! The "right" interpretation is whatever is most useful at the moment.

5. But that's the point. Duality is useful as a different view of looking at things, but that's what I want to know: what's a good example of how the "alternate" view makes something easier.

Posted by Suresh

6. If you are not restricted to geometry problems, isn't the max-flow min-cut theorem such an example? To certify that a flow is optimal, you need the dual and vice versa. Is there any other way of showing that your augmenting path algorithm terminates with an optimal flow?

Yao's minimax principle is a more subtle example. It seems hard to show a lower bound on (say) the competitive ratio of a randomized online algorithm. Looking at the dual (performance of a deterministic algorithm on a distribution over inputs) makes it much easier.

--kunal

7. true, but that's why I excluded optimization problems, where almost by definition you need the certificate that the dual provides.

I guess what I am trying to get at is a more basic view of duality, from a purely geometric/algebraic perspective. the truth is that I am not sure what I'm looking for till I see it :)

Posted by Suresh

8. For the flow problem, take the union of your flow and optimal flow. Also, reverse the edges of your flow. If the value of your flow < optimal flow, this graph will contain a augmenting path. You do not need the bound of the value of the cut in the original graph.

Posted by Anonymous

9. With every day, and from both sides of my intelligence, the moral and the intellectual, I thus drew steadily nearer to that truth, by whose partial discovery I have been doomed to such a dreadful shipwreck: that man is not truly one, but truly two. I say two, because the state of my own knowledge does not pass beyond that point. Others will follow, others will outstrip me on the same lines; and I hazard the guess that man will be ultimately known for a mere polity of multifarious, incongruous and independent denizens. I, for my part, from the nature of my life, advanced infallibly in one direction and in one direction only. It was on the moral side, and in my own person, that I learned to recognise the thorough and primitive duality of man; I saw that, of the two natures that contended in the field of my consciousness, even if I could rightly be said to be either, it was only because I was radically both; and from an early date, even before the course of my scientific discoveries had begun to suggest the most naked possibility of such a miracle, I had learned to dwell with pleasure, as a beloved daydream, on the thought of the separation of these elements. If each, I told myself, could be housed in separate identities, life would be relieved of all that was unbearable; the unjust might go his way, delivered from the aspirations and remorse of his more upright twin; and the just could walk steadfastly and securely on his upward path, doing the good things in which he found his pleasure, and no longer exposed to disgrace and penitence by the hands of this extraneous evil. It was the curse of mankind that these incongruous faggots were thus bound together -- that in the agonised womb of consciousness, these polar twins should be continuously struggling. How, then were they dissociated?
Dr. Jekyll
Posted by Dr. Jekyll