Erdos' Combinatorial Geometry Problem Solved

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."

Comments

Ham sandwich???

[gstoddart]

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???

[Anonymous Coward]

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.

Re:Ham sandwich???

[werepants]

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:Ham sandwich???

[CyberDragon777]

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

Re:Ham sandwich???

[ClickOnThis]

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

Re:Ham sandwich???

[khallow]

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".

The thing about bisections into equal volumes, is that it happens to be particularly parsimonious. That is, it requires very little information to define the concept and design an algorithm which yields the desired bisection. Further, it is stable, that is, you can tweak the definitions a little (there are concrete ways in which you can define that) and get bisections which are close (again defined in concrete ways) to the equal volume bisections.

Real-world applications?

[Jugalator]

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:Real-world applications?

[intellitech]

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:Real-world applications?

[gstoddart]

+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.

Subtraction

[bunratty]

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:Subtraction

[bunratty]

Ah, eldavojohn, posting math research stories but unable to do subtraction.

Mildly Ambiguous

[mathcam]

Saying "Paul Erdos' combinatorial problem" is like saying "Michael Jordan's dunk he made that one time."

Re:Mildly Ambiguous

[Anonymous Coward]

Saying "Michael Jordan's dunk he made that one time." is a little bit like saying "Paul Erdos' combinatorial problem".

Example of It in Use

[eldavojohn]

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. Also, I screwed up the summary, the reward was offered in '46 not '35.

Re:Example of It in Use

[gstoddart]

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 and John Tukey, 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. Here the "objects" should be sets of finite measure (or, in fact, just of finite outer measure) for the notion of "dividing the volume in half" to make sense.

So, cutting a sandwich in half, but expanded to a higher number of dimensions. 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).

Re:Example of It in Use

[WhirlwindMonk]

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:Example of It in Use

[davester666]

to go along with the six degree's of bacon!

Re:Polynomial ham sandwich theorem?

[RevWaldo]

Doesn't sound very kosher to me....

.

Actual authors

[domulys]

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:Polynomial ham sandwich theorem?

[_0xd0ad]

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.

Ham Sandwich Theorem

[anwaya]

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 states that you can divide n finitely measurable objects in n-space with an n-1 dimensional hyperplane.

Re:Ham Sandwich Theorem

[_0xd0ad]

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

Erdos Prizes

[SoVeryTired]

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.

Show me the money!

[Xer0ss]

Well shit. If I had known there was 500 bucks on the line I would have given it a shot!

Thanks for the Reminder

[eldavojohn]

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 anymore.

Re:Mathematics

[Webs 101]

I was friends with Nets when we were undergrads. He was just Nets Katz, then. Hawk is a translation of his Hebrew name "Nets".