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

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.

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