Jump to content

Wikipedia:Featured picture candidates/Shapley–Folkman lemma

Add links
From Wikipedia, the free encyclopedia

Shapley–Folkman lemma

[edit]

Voting period is over. Please don't add any new votes. Voting period ends on 12 Nov 2012 at 10:32:28 (UTC)

Original – The Shapley–Folkman lemma is illustrated by the Minkowski addition of four sets. The point (+) in the convex hull of the Minkowski sum of the four non-convex sets (right) is the sum of four points (+) from the (left-hand) sets—two points in two non-convex sets plus two points in the convex hulls of two sets. The convex hulls are shaded pink. The original sets each have exactly two points (shown as red dots).
Reason
This is the best illustration of the Shapley–Folkman lemma in human history. Shapley's 2012 receipt of the Nobel Prize in Economics (to be awarded in December) makes this topical.
Articles in which this image appears
Shapley–Folkman lemma, Minkowski addition, Zonohedron (Zonotope), oriented matroid, Ivar Ekeland.
FP category for this image
Mathematics
Creator
David Eppstein
I'm afraid I still find this unintelligible. I have no idea at all what this diagram is supposed to be illustrating. 86.146.108.178 (talk) 00:05, 6 November 2012 (UTC)[reply]
  • Comment Its taken me a while to understand the picture. It wasn't until I got down to Shapley–Folkman lemma#Statements that in became clear. The statement which made it clear was if a point x lies in the convex hull of the Minkowski sum of N sets then x lies in the sum of the convex hulls of the summand-sets. Even that needs some decoding, first take the four sets on the left which consist of two points each. Take all posible sums of points from each set (the Minkowski sum) this gives the 16 red dots on the left. Next form the convex hull, imaging stretching a rubber band around all the points, the convex hull is all the points inside the band, this gives the pink region on the right. The convex hull of each of the sets on the left is just the pink lines joining the dots. Finally we get to the lemma, take any point in the pink region on the right, this must be the sum of four points on the pink lines on the left. This is illustrated by the + signs.
As to the actual image, one you understand the lemma it is a very elegant illustration. However, it maybe a bit too concise, trying to put everything in one diagram, which is a impressive feet, may make it a bit harder to follow. The steps could be broken down into 4 or 6 images. A) the four sets, just with the dots, B) their Minkowski sum - the 16 dots on right, C) & D) convex hulls of A) & B), E) & F) final pic with + signs. A caption making it clear that the 16 dots on the right is the MS of the sets on the left might also help. --Salix (talk): 00:47, 6 November 2012 (UTC)[reply]
Thanks for the substantial comments. :) The statement that the convex hull of the sum is the sum of the convex hulls is a preliminary result, not the Shapley Folkman lemma (which states that an even more surprising fact, which is illustrated by David's drawing)! Kiefer.Wolfowitz 16:54, 6 November 2012 (UTC)[reply]
Ah get it now. As the dimension of problem is 2 the point must be the sum of four points only 2 of which can be in the convex hulls.
Rather than a featured picture I think this would be a good candidate for the Picture of the Month in Portal:Mathematics. It would need a much improved caption so its clear what the statement of the lemma really is. Maths picture of the month does allow for a more extensive caption. Its also worth pointing out the significance of the lemma as Shapley won the 2012 Nobel Memorial Prize in Economic Sciences.--Salix (talk): 12:35, 7 November 2012 (UTC)[reply]
Rather than "can be", you mean "need be", I think. :)
The criteria for featured pictures do not include general accessibility, as far as I read. Would you, Tomcat, or the IP link this policy, please? Kiefer.Wolfowitz 17:59, 7 November 2012 (UTC)[reply]
My knowledge of Wikipedia policy does not extend that far I'm afraid! However, I would argue that the image has no great intrinsic skill or merit, and is something that anyone with a basic familiarity with computer drawing packages could easily produce. Therefore, its only potential claim to fame* is its explanatory power, and I currently find its explanatory power conspicuously lacking. You could say it explains the theorem to people who already understand it, but is unintelligible to people who don't. 86.167.19.237 (talk) 21:27, 7 November 2012 (UTC) * I mean, in a "featured picture" sense. I'm sure it is a very worthwhile addition to the article itself...[reply]
David's picture was the first and may be the only illustration of the Shapley-Folkman lemma in world literature. You can see some hand-waving illustrations of the "convexification on average of Minkowski addition" in Mas-Colell's New Palgrave article on convexity and in Dimitri Bertsekas's book on nonlinear programming (cited in our SF lemma article), but there may still be no other illustration of the SF lemma---certainly not before Eppstein's picture (2010).
The criterion for judging pictures is the picture's contribution to the article, not the accessibility of the mathematical theorem (or the technique needed to produce this illustration, once David has made the conceptual break-throughs). David is a Professor of Computer Science who specializes in computational geometry, and I suspect that his use of colors, etc., rewards attention.
I thank you for ending the paragraph with a conciliatory sentence. Indeed, de gustibus non est disputandum. Kiefer.Wolfowitz 22:03, 7 November 2012 (UTC)[reply]
Right, it may be that I am misunderstanding the scope of the "featured picture" award. I imagined featured pictures ought to be of fairly wide appeal and interest, and accessible, at least on some level, to most people reading the encyclopedia. If that's not the case then my objections on the grounds that almost everyone won't understand it go away. 86.167.19.237 (talk) 00:09, 8 November 2012 (UTC)[reply]
  • Weak Support Yes, it does illustrate the lemma. But I'm not convinced it does so really clearly. The example given in the text of article is much easier to understand ('The Shapley–Folkman lemma implies, for example, that every point in [0, 2] is the sum of an integer from {0, 1} and a real number from [0, 1]'). JJ Harrison (talk) 13:03, 10 November 2012 (UTC)[reply]
    A one-dimension illustration on a two-dimensional computer-screen would not capture the imagination.Kiefer.Wolfowitz 13:16, 10 November 2012 (UTC)[reply]

My support is weak because I think three points in the plane might be less confusing.

I suppose that you mean three pairs of points (to be summed).
The lemma states a proposition that depends on the dimension of the space and not on the number of summands. So having four summands illustrates this take-home message, which is the reason that this lemma is so important in economics.
I had the same thought. :) However, Three pairs of distinct points (having line segments as their convex hulls) would be simpler, yet three summands do not lend themselves to symmetric graphical-representation. David's four-windows treat the four summands symmetrically. Kiefer.Wolfowitz 13:10, 10 November 2012 (UTC)[reply]


Not Promoted --Makeemlighter (talk) 00:21, 13 November 2012 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Wikipedia:Featured_picture_candidates/Shapley–Folkman_lemma&oldid=1136455980"