typodupeerror

## Erdos' Combinatorial Geometry Problem Solved170

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."
This discussion has been archived. No new comments can be posted.

## Erdos' Combinatorial Geometry Problem Solved

• #### Finally I can sleep! (Score:1)

Showing absolute ignorance here, but anyone else think the "polynomial ham sandwich theorem" sounds like it was perhaps concocted by someone overweight?
• #### 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)

on Friday February 25, 2011 @11:17AM (#35312206) Homepage

like using the polynomial ham sandwich theorem

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)

by Anonymous Coward on Friday February 25, 2011 @11:26AM (#35312316)

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)

<eldavojohn&gmail,com> on Friday February 25, 2011 @11:33AM (#35312396) Journal
The Fields Medal winner named in the article has a blog about using it to prove the Szemeredi-Trotter theorem [wordpress.com] and of course there's the wikipedia article [wikipedia.org] on the generalized form of it. Also, I screwed up the summary, the reward was offered in '46 not '35.
• #### Re: (Score:3)

The Fields Medal winner named in the article has a blog about using it to prove the Szemeredi-Trotter theorem and of course there's the wikipedia article on the generalized form of it.

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:

In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone-Tukey theorem after Arthur H. Stone

• #### 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)

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.

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)

I think we all know where this is heading, so I'm just going to say it: Seven-dimensional hyper-bacon.
Dare to dream.
• #### Re: (Score:2)

I think we all know where this is heading, so I'm just going to say it: Seven-dimensional hyper-bacon.
Dare to dream.

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)

Contingent on my alcohol intake, my counter-top can have 3-D, 4-D and 5-D dimensions. And scary green monsters on top.

That's not alcohol ... that's something out of a Hunter S. Thompson novel. :-P

• #### 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:3)

A mathematician is a machine that turns ham sandwiches into ... uh, never mind.

• #### Re: (Score:2)

Into coffee, thus reducing it to a previously solved joke.
• #### 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)

As a really (really) rough idea: For any 3d objects of finite size, there exists a plane which could bisect all three of them.

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)

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.

• #### Mathematics (Score:2)

As someone not well versed in the field of mathematical proofs, all I can really add to this discussion is that "Nets Hawk Katz" is a really cool name.
• #### Re:Mathematics (Score:4, Interesting)

on Friday February 25, 2011 @01:26PM (#35313664) Homepage
I was friends with Nets when we were undergrads. He was just Nets Katz, then. Hawk is a translation of his Hebrew name "Nets".
• #### Re: (Score:2)

Nets Hawk Katz looked to me like an anagram. But the only anagram I could find of this was Hawk Tank Zest.
• #### Real-world applications? (Score:3)

on Friday February 25, 2011 @11:18AM (#35312216) Journal

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)

Yes, but you'll have to refer to Nash theory in order for everybody in your group to get one in the first place.

Ignore the hot blond, go for her plainer friends.

Words to live by.

• #### Re: (Score:2)

+1 Insightful. They want attention too and are usually more willing to work for it.
• #### Re: (Score:3)

+1 Insightful. They want attention too and are usually more willing to work for it.

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)

Most likely, however the process of entering all of those parameters into a computer might have an undesired side effect on the set of girls in question.
• #### Re: (Score:1)

When you define your set of interesting girls, you need to watch out for the Axiom of Choice. It's known to make things like this quite complicated.
• #### 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:

• #### 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)

on Friday February 25, 2011 @11:22AM (#35312272)
The reward was posted in 1935 but it's been solved after 65 years? Someone needs to brush up on their subtraction or current events -- the year is currently 2011. I don't think I would trust the person who made that mistake to accurately explain this advanced mathematical research.
• #### Re: (Score:1)

by Anonymous Coward

Summary is incorrect. TFA says 1946, which would be 65 years.

• #### Re:Subtraction (Score:5, Funny)

on Friday February 25, 2011 @11:31AM (#35312380)
Ah, eldavojohn, posting math research stories but unable to do subtraction.
• #### 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)

According to TFA, the problem was originally posed by Erdos in 1946.
• #### Mildly Ambiguous (Score:3, Insightful)

on Friday February 25, 2011 @11:30AM (#35312368)
Saying "Paul Erdos' combinatorial problem" is like saying "Michael Jordan's dunk he made that one time."
• #### Re: (Score:1)

I'm sorry, I'm a geek; I don't understand sports metaphors. :-)

• #### Re: (Score:2, Funny)

by Anonymous Coward

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)

In mathematics they alphabetize authors so there is no assumption of primary, secondary, etc.

• #### 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).

• #### 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)

Oh, you've read the synopsis? :)
• #### Bonus! (Score:1)

He should get bonus points for style with the name "Nets Hawk Katz"
• #### Show me the money! (Score:2)

Well shit. If I had known there was 500 bucks on the line I would have given it a shot!
• #### 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)

It's supposed to be a 2D problem yet there is not a single graph in the proof. I don't think they found the theorem using mathemical formulas alone. I wish they were more graphics to show the origin of the problem and its connection to the real world.
• #### Graphics? (Score:2)

The summary mentions that this is useful for computer graphics. Can someone elaborate?
• #### 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)

I have an MSc in CS specializing in computer graphics, but my specific area is in rendering, not computational geometry. My real question is then, is this useful for rendering specifically?

#### Related LinksTop of the: day, week, month.

Things are not as simple as they seems at first. - Edward Thorp

Working...