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.
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.
ReplyDeletePosted by Anonymous
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.
ReplyDeletePosted by Anonymous
Dey's k-set upper bound? Switches back and forth a couple times if I remember correctly.
ReplyDeleteBut 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.
ReplyDeletePosted by Suresh
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?
ReplyDeleteYao'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
true, but that's why I excluded optimization problems, where almost by definition you need the certificate that the dual provides.
ReplyDeleteI 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
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.
ReplyDeletePosted by Anonymous
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?
ReplyDeleteDr. Jekyll
Posted by Dr. Jekyll