Erdos' Combinatorial Geometry Problem Solved 170
eldavojohn writes "After 65 years, Paul Erdos' combinatorial problem has been solved by Indiana University professor Nets Hawk Katz. The problem involved determining the minimum number of distinct distances between any finite set of points in a plane and its applications range from drug development to robot motion planning to computer graphics. You can find a description of the problem here and the prepublication of the paper on arXiv. The researchers used the existing work on the problem and included two new ideas of their own, like using the polynomial ham sandwich theorem, to reach a solution that warranted at least half of Erdos' $500 reward posted for solving this problem way back in 1935."
Finally I can sleep! (Score:1)
Re: (Score:2)
Showing absolute ignorance here, but anyone else think the "polynomial ham sandwich theorem" sounds like it was perhaps concocted by someone overweight?
...or someone starving.
Ham sandwich??? (Score:5, Funny)
Really? That's the coolest name for something I don't understand ever.
Hell, I'd have posted some of the google links to try to explain WTF it means ... but, quite frankly, I have no idea what any of them say. Can anybody put this wonderful sounding theorem into something that a layman has at least a passing chance of getting the gist of?
I'm sure whatever else the authors did was cool, but frickin' ham sammiches ... in math!! Awesome!
Re:Ham sandwich??? (Score:5, Informative)
Ham Sandwich theorem says that if you have n objects in n dimensional space, you can cut them all in half with a cut using an n-1 dimensional surface.
It's called Ham Sandwich because the analogy says if you have a chunk of ham, a chunk of cheese, and a chunk of bread (n = 3) in 3-D space, you can make a single "cut" to cut them all in exactly half. This single cut is achieved by finding the plane (3-1 = 2 dimensions) that goes through all of them.
Alternately, there's Pancake theorem that says if you have two flat pancakes on a 2-D surface (like on your countertop), there's a single line (1-D) that can cut both pancakes exactly in half. That might be easier to think of.
Example of It in Use (Score:5, Informative)
Re: (Score:3)
You know, when I googled for "Ham Sandwich Theorem", wiki didn't even show up in the first page, so I assumed there wasn't one.
Oddly enough, the first paragraph nicely summarized what it boils down to:
Re: (Score:2)
Specifically, where the number of objects corresponds to the number of dimensions -- so, by crude extension, add lettuce, tomato and cheese to your sandwich and do it in six dimensions (yes, I know, that is a horrible over-simplification and I can't think of a car analogy).
When expanding beyond three dimensions, you have to prefix the word "hyper" onto all objects. So you would add "hyper-lettuce," "hyper-tomato," and "hyper-cheese." Or if you really want to be exact, "six-dimensional hyper-lettuce," etc.
Re: (Score:2)
Six-dimensional hyper-ham ... I know people who would weep tears of joy at those words.
Re: (Score:2)
Six-dimensional hyper-ham
I don't think that's a kosher example...
Re: (Score:2)
Dare to dream.
Re: (Score:2)
Sorry, but I think that might open up a rift in the pork-time continuum.
Re: (Score:2)
to go along with the six degree's of bacon!
Erdos Prizes (Score:3)
Erdos offered many prizes for the solution of problems that he thought were difficult or out of reach of the mathematics of his time. These prizes were sometimes huge, worth tens or even hundreds of thousands of US dollars in today's money.
Erdos used to joke that he would get in trouble for violating minimum wage laws.
Re: (Score:2)
Erdos offered many prizes for the solution of problems that he thought were difficult or out of reach of the mathematics of his time. These prizes were sometimes huge, worth tens or even hundreds of thousands of US dollars in today's money.
Erdos used to joke that he would get in trouble for violating minimum wage laws.
Too bad he didn't put that $500 in some kind of long-term savings instrument. $500 in 1935 at 5% compounded annually = $20,387.16 in 2011.
If you believe the stock market truly compounds at 10.5% annually over the long haul, then $500 in 1936 at 10.5% compounded annually = $987,422.76 in 2011.
Of course, he could have just waited a few years and bought 5,000 copies of Superman's first appearance in Action #1 and encased them in argon.
Since I live in Abstract Hilbert Space (Score:2)
I have no idea how to cut the sandwich . . . I can't even manage to find the bugger: http://en.wikipedia.org/wiki/Hilbert_space [wikipedia.org]
Ham Sandwich theorem says that if you have n objects in n dimensional space, you can cut them all in half with a cut using an n-1 dimensional surface.
It's called Ham Sandwich because the analogy says if you have a chunk of ham, a chunk of cheese, and a chunk of bread (n = 3) in 3-D space, you can make a single "cut" to cut them all in exactly half. This single cut is achieved by finding the plane (3-1 = 2 dimensions) that goes through all of them.
Alternately, there's Pancake theorem that says if you have two flat pancakes on a 2-D surface (like on your countertop), there's a single line (1-D) that can cut both pancakes exactly in half. That might be easier to think of.
Does the pancake come with bacon?
Contingent on my alcohol intake, my counter-top can have 3-D, 4-D and 5-D dimensions. And scary green monsters on top. I guess that they like ham sandwiches . . . and pancakes,
Re: (Score:2)
That's not alcohol ... that's something out of a Hunter S. Thompson novel. :-P
Re: (Score:2)
examples of Hilbert spaces include spaces of square-integrable functions, spaces of sequences, Sobolev spaces consisting of generalized functions, and Hardy spaces of holomorphic functions.
Well, that pretty much describes the closet where my girlfriend keeps her shoes. I call it Fibber McGee's closet, but she is German, and doesn't understand the joke: http://en.wikipedia.org/wiki/Fibber_McGee_and_Molly#The_Closet [wikipedia.org]
It is a simple radio gag, but I still laugh my ass off whenever I hear it. "Oh, Molly, I'll get that, it must be here in my closet . . ."
Re: (Score:2)
Assuming that "cutting in half" means cutting through the center of mass, doesn't that boil down to saying that two points define a line (1D) in 2-space, three points define a plane (2D) in 3-space, etc? Or is there a subtlety I'm missing here?
Re: (Score:1)
Cutting in half means splitting in two parts of equal volume.
So the "top half" of Mt. Everest is obviously of equal volume to the "bottom half"?
Re: (Score:2)
Re: (Score:1)
Of course you can bisect anything by volume. But is it obvious that you ought to? Most people, I suspect, would logically bisect Mt. Everest into "top" and "bottom" halves by altitude, not by volume. I was countering Anonymous Coward's claim that the "obvious" way to bisect something is by volume.
If we approximated Mt. Everest as a perfect sphere of constant density, it wouldn't matter how you bisected it, because no matter which method you selected (height, cross-sectional area, volume, or mass) they would
Re: (Score:3)
But is it obvious that you ought to?
Depends how you define "bisect". A usable definition gets you one or more "obvious optimizations" for free.
This is a subtle issue in mathematics. Vaguely defined operations on vague objects generally go nowhere. Concrete, well-defined stuff gives you both a working problem and insight in what are the real issues.
Nothing aside from your own diligence keeps you from making thousands or millions of rival mathematical definitions of objects and bisections. These are all valid and all just as "obvious".
Re: (Score:2)
What you're saying amounts to "but it's easier this way".
Yes, to such a degree that it is the difference between impossible and possible.
bisecting it into halves of equal volume would require, at the least, two pictures from different angles to give me a rough idea of its 3-dimensional shape.
You only know part of its shape. What is the shape of the part you can't see from the surface? does it get lopped off at the base, where the crust begins a few dozen km down, or is it a wedge straight to the core of the Earth?
Second, do you have a consist way to bisect this object? Or do you cut it differently each time you try?
It makes the most sense to take into consideration as many different properties as possible, because you can always just assign them constant values later and they'll fall out of the equation. If you define bisection in terms of bisecting something by mass, you can always simply assume that the density is near-uniform... lo and behold, now you're bisecting by volume.
And if you're bisecting by mood, you can just hang it up, until you get rid of that variable. You c
Re: (Score:2)
What you're saying amounts to "but it's too hard".
And what makes you think that's not a valid excuse? Too hard problems whip my ass all the time. I can beat my head on the immovable wall or I can try simplifications to see if I can get anywhere with that strategy.
Yes... because it's extremely hard to define a theoretical model to describe how you bisect something by mass. So hard, in fact, that scientists should just pretend mass doesn't exist and approximate everything as a uniform-density solid of a particular volume and shape.
Let's give a counterexample. We have three bounded measurable objects in three dimensional space which are not constant density. If they were, a plane could bisect them, splitting them into equal volume sets.
Now it turns out that I can use this result directly to prove the same for objects with
Re: (Score:2)
If the problem is to cut objects into equal volumes, then it doesn't make sense to define bisection in some way that is irrelevant to the problem.
Now maybe they were claiming that there was a "right way" to bisect (though that's
Re: (Score:3)
A mathematician is a machine that turns ham sandwiches into ... uh, never mind.
Re: (Score:2)
Re: (Score:2)
You know, I was considering posting a snarky comment to that effect when it occurred to me that they probably couldn't. I barely appreciate the subtleties of the problem (that is, why it's hard).
This is the kind of proof I could maybe understand in my Algorithms class, given a week and a very good explanation. But I'm not exactly a 'layman' in that context...
Though I will agree - the polynomial ham sandwich theorem sounds badass.
Re: (Score:2)
Disclaimer:
IANAMBITCO (I am not a mathemetician, but I took calculus once)
Re: (Score:2)
You also encounter the ham sandwich in some logic / philosophy classes, as follows.
Proposition
A ham sandwich is better than eternal happiness
Proof
- A ham sandwich is better than nothing.
- Nothing is better than eternal happiness.
- Therefore, a ham sandwich is better than eternal happiness. QED.
Re: (Score:1)
If the subjective states of "better" and "worse" are defined in such a way that "nothing" is, in fact, preferred over "eternal happiness", then yes, a ham sandwich is "better" than eternal happiness.
For instance, if the problem is referring to someone you hate, you'd prefer them to have a ham sandwich instead. Especially if they can't eat pork.
Re: (Score:2)
While you are correct, the logic problem in the proof is not quite so recondite. Think set theory.
Re: (Score:1)
Actually "Nothing is better than eternal happiness" is a way of saying "Eternal happiness is at least as good as anything else". It doesn't have to be better.
BUSTED! IN YOUR FACE!
Re: (Score:1)
The Polynomial Ham Sandwich Theorem!
The ham sandwich theorem, states that given n measurable "objects" in n-dimensional space, it is possible to divide all of them in half (according to volume) with a single (n - 1)-dimensional hyperplane.
The ham sandwich theorem takes its name from the case when n = 3 and the three objects of any shape are a chunk of ham, a hunk of cheese, and a piece of bread -- notionally, a sandwich -- which can then each be bisected with a single cut (i.e., a plane). The theorem then
Re: (Score:1)
The Sandwich Theorem in common terms:
If you have a function (the "ham") whose known values lie between two other functions (the "bread") and you are taking a limit at a point, then the limit of the "ham" is bounded by the limits of the "bread". They'll usually make some reference about the point you're taking the limit at as being where you're biting (or squeezing) the sandwich at.
Of course, it is nicest when the two limits for the bread are the same (hence the "squeezing"), but the bounds could still be us
Re: (Score:2)
Can I sue a polynomial ham sandwich?
Really though, I was just posting to point out how many Maths geeks point to /. as AC. Interesting correlation.
Or maybe it's one Nash-type genius, I dunno.
Re: (Score:2)
Actually it's Erdo"s.
(Support Unicode already Slashdot!)
Erdo" is Forest in Hungarian, and Erdo"s would be "Foresty".
http://en.wikipedia.org/wiki/Paul_Erd%C5%91s [wikipedia.org]
Mathematics (Score:2)
Re:Mathematics (Score:4, Interesting)
Re: (Score:2)
Re: (Score:2)
Real-world applications? (Score:3)
The problem involved determining the minimum number of distinct distances between any finite set of points in a plane
So will this assist me in traversing a crowded pub more effeciently to get me more quickly to a well-defined set of interesting girls, according to my parameters?
Re: (Score:3)
Yes, but you'll have to refer to Nash theory in order for everybody in your group to get one in the first place.
Re: (Score:2)
Ignore the hot blond, go for her plainer friends.
Words to live by.
Re: (Score:2)
Re: (Score:3)
And, if you all go for the hot blond, get shot down, and then go for her friends ... they'll all know they were second choices and be unhappy about it.
Pretty much what the poster meant when he said the Nash theorem.
Re: (Score:2)
Yes yes, we all saw the movie too.
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
Yeah, but if you accept the Axiom of Choice, you can decompose the hot girl and recompose the non-discrete pieces into two hot girls, each equal to the original!
Next problem on his list (Score:2)
He is working on Einstein's Tonsorial Problem:
http://www.math.indiana.edu/people/profile.phtml?id=nhkatz [indiana.edu]
Re: (Score:2)
Next problem on his list :
He is working on Einstein's Tonsorial Problem
Really? There is a more generalized version of this problem that extends into higher dimensions. I figured he would have been working on extending the solution into dimensions >= 3. Maybe it's only tenured academics that milk such things for all they're worth.
Subtraction (Score:3)
Re: (Score:1)
Summary is incorrect. TFA says 1946, which would be 65 years.
Re:Subtraction (Score:5, Funny)
Thanks for the Reminder (Score:3)
Ah, eldavojohn, posting math research stories but unable to do subtraction.
Don't worry, I only posted it here because I was unable to post it to reddit due to heavy usage. You won't have to put up with me or my apologies [slashdot.org] anymore.
Re: (Score:2)
Mildly Ambiguous (Score:3, Insightful)
Re: (Score:1)
I'm sorry, I'm a geek; I don't understand sports metaphors. :-)
Re: (Score:2, Funny)
Saying "Michael Jordan's dunk he made that one time." is a little bit like saying "Paul Erdos' combinatorial problem".
Re: (Score:2)
that's the funniest thing on here in 9 years.
Re: (Score:1)
And... for those of us who are neither scientists nor athletes (which should be pretty much all of us)... it's a bit like saying "Ford's truck model they built that one year".
Re: (Score:2)
Thank you. It's sad that I had to get 70% of the way through the comments before I found one which actually recognised this obvious fact.
Actual authors (Score:2)
After 65 years, Paul Erdos' combinatorial problem has been solved by Indiana University professor Nets Hawk Katz.
It was actually solved by Larry Guth and Nets Hawk Katz. Not sure how it is that authors magically disappear from press releases, especially principal authors...
Re: (Score:1)
It was actually solved by Larry Guth and Nets Hawk Katz. Not sure how it is that authors magically disappear from press releases, especially principal authors...
Larry Guth seems to be some sort of graduate student, though it's not clear that that's so. That would certainly explain it, however. Graduate students are scum compared to the professors. Didn't you know that?
Re: (Score:1)
Re: (Score:2)
The article is about Katz, published by Indiana University.
Ham Sandwich Theorem (Score:2)
The Stone–Tukey version of this theorem is a generalization of a simple case.
Consider a ham sandwich, with two slices of bread around a slice of ham. Each of these components has a center of gravity, and if you slice any one of these with a plane that passes through the center of gravity, then the two halves will be equal in mass.
Three points in 3-space define a plane, so the unique plane that passes through the three centers of gravity divides both slices of bread and the ham in half.
The general case
Re: (Score:2)
Seems like you know what you are doing. What the heck is "distinct distance"? Is it the number of distances larger than some characteristic distance of this set (average, diameter, etc.)?
Re: (Score:2)
center of gravity ... mass
I'm not sure which makes me want to slap you more... the fact that you needlessly restricted the attribute of matter to its "center of gravity" instead of its "center of mass", or the fact that you then relaxed back to the general word "mass" in referring to the property which you'd just indicated was specifically its gravitational mass.
/pedant
Re: (Score:2)
So... does that change the meaning of what he said? The centre of gravitational mass will be the same point as the centre of mass.
In reference to your reply to Noughmad, the ham sandwich theorem deals with volume rather than with mass, so referring to the centre of volume would be more directly attributable to the topic at hand.
Re: (Score:2)
Excellent description, and it helped me understand it, but I have a minor correction.
The plane that cuts the three pieces (or the nth-dimension generalization that cuts n pieces) isn't necessarily unique, specifically in the case where the three points are colinear (or the nth-dimension generalization thereof).
Re: (Score:1)
A plane is a 2D surface, therefore it is flat.
Re: (Score:2)
The centers of mass do not have to be aligned, if by aligned you mean that they lie on a straight line. They just all have to lie on a plane, which is always true of any three points - unless they all lie on a straight line or coincide, and in either of these cases there is an infinite number of planes that bisect.
Re: (Score:1)
Why would you want to divide a sandwich by volume? To check you'd have to dunk it in water and then it'd be all soggy. Gross.
You divide it into halves by weight, and then you check it with a grocer's scale, dummy.
Re: (Score:2)
A volume of uniform (non-zero) density has a center of volume at the same place as the center of mass.
These names (Score:2)
What is it with scientists and mathematicians and their crazy names? Nets Hawk Catz? Ham Sandwich Theorem?
What's next, a Ninja Pirate Zombie Fractal theorem written by Buster Rabbits?
Re: (Score:2)
Bonus! (Score:1)
Show me the money! (Score:2)
Elegant Simplicity (Score:2)
For being such a complex problem, the solution seems rather simple.
Guess it's one of those "Right in front of us the whole time" answers.
Graphics? (Score:1)
Graphics? (Score:2)
Re: (Score:2)
A lot of computer graphics, especially the field of Computational Geometry, deals with sorting points and lines, finding the closest convex shape around a set of points and stuff like that. All these things are used in algorithms to draw 3D-objects faster, or detect collisions between objects, etc.
You'd need a specialist to answer the question as to what actual use this will be put - but theorems like this form the underpinnings of all computer graphics beyond just putting a few pixels on a 2D-plane.
Re: (Score:2)
Re:Polynomial ham sandwich theorem? (Score:5, Funny)
.
Re: (Score:1)
Actually it's a theorem that was postulated by a pig named Ben who ruminated for a while and realised that in 4-space pigs would be kosher because there would be a specific 3-dimensional hyperplane which would split their 4 feet precisely in halves.
Re: (Score:1)
Except, of course, it isn't their feet that make them not-Kosher. /feels a strange blast of air over-head.
Re: (Score:1)
Yeah... of the two applicable requirements for kosher (cloven hooves and ruminating), pigs actually do have cloven hooves.
It was kinda backward but I don't know how to make it into a proper joke the correct way. :/
Re: (Score:2)
Well, the "polynomial brisket sandwich" problem sounds more complicated, and the "polynomial reuben sandwich" actually involves a greater number of objects due to the increased number of pieces of meat, the sauerkraut and the pickle ... so it's actually higher complexity. You could wave away some of that by saying the meat is all one "piece" for purposed of discussion, but that might only appease the physicists and engineers.
It's only hypothetical ham, it's OK.
Re: (Score:2)
You could wave away some of that by saying the meat is all one "piece" for purposed of discussion, but that might only appease the physicists and engineers.
No, the physicists have already approximated the pieces as point masses and they are all trying to figure out why you want to cut them in half.
Re: (Score:2)
Isn't brisket topologically congruent to ham? Reubens, yeah, they're more complex, especially with the potential for knots in the sauerkraut, but ham and brisket are usually just slices....
Re: (Score:2)
Re: (Score:2)
Sadly, some of us know this, but apparently even grammar experts seem to think it doesn't apply anymore. I actually disagreed out loud to my copy of Eats, Shoots, and Leaves [wikipedia.org] when she said to not do it that way.
Given how thoroughly drilled into my be rather stern old teachers, I still cringe when I see it used wrong.
Re: (Score:2)
also, his name is not written like that. I would write the correct spelling, but this frakup called slashcode can't get utf-8 right in 2011.
Re: (Score:1)
Re: (Score:2)
The first bloody paragraph of Strunk and bloody White.
Yes, and that's only one of the many many things that misguided and horribly out-of-date book is wrong about.
This post [upenn.edu] by Prof. Arnold Zwicky (Linguistics, Stanford) only gives a hint of how much that little book is loathed by people who actually know something about language and style. Especially on the other side of the pond where many of its "rules" were never ever considered correct.
Strunk & White is to language as BASIC is to programming--you can learn something from it, but it's likely to cause da
Re: (Score:2)
There are so many bad/clueless style guides out there that sheer quantity doesn't really say much. The Chicago Manual of Style—one of the few really widely-respected guides to American English style and usage—recommends using the apostrophe with 's', but explicitly says that just the apostrophe is not incorrect. (This is a change from the previous edition where they didn't even state a preference.)
Re: (Score:2)
Can we finally kill the idea that orthography is part of grammar?
Re: (Score:2)
According to whom? From the Chicago Manual of Style FAQ [chicagomanualofstyle.org]:
Q. Which is the correct singular possessive form? “Professor Davis’ class” or “Professor Davis’s class”? [...]
A. In its 15th edition, CMOS allowed the style shown in your first example, but the new 16th edition (7.21) no longer recommends it, although it is not incorrect...