The Happy Ending Problem [video] | Hacker News Reader

The Happy Ending Problem [video]

numberphile.com

57 pointsColinWright17 comments

Reminds me of VC dimension kind of stuff for describing binary classifiers.

That first example w/ 5 points necessitating a convex 4 sided polygon is like the VC dimension proof that an axis aligned rectangle can never correctly classify 5 points, since you can never arrange 5 points w/o one of them being in the body of a rectangular region surrounding the other 4 (and that interior point's label therefore can't be arbitrary and still correctly classified). more: https://www.cs.princeton.edu/courses/archive/spring13/cos511...

Wonder if the 2^(n-2) + 1 rule is somewhere in the VC dim lit

I love graphs!

For those who found this interesting or inspiring check out "Graph Theory" by W. T. Tutte -- it's an exceptional book for those scarred by mathematics in elementary or secondary school and want a refresher to show them how cool it is.

This isn't actually graph theory, because the position in 2D space matters here. In graph theory the actual placement of the vertices is irrelevant - the only thing that matters is which ones are joined.

But I share your enthusiasm - my PhD is in graph theory.

Right, it's a geometrical problem... my suggestion is a bit of a tangent.

It kind of feels - in my mathematical nativity - that there must be a general way to reduce all higher n down to the proof given for n=4 rather like Euler solved the Königsberg problem.

I presume to earn this prize, one need provide a formal proof. I've never been one for formal math proofs, but I think I could formulate a brute force test...

So you can formulate a brute force test that works for all n? That's a bold claim. Remember, you are trying to prove that for every natural number n, once you have 2^(n-2)+1 points in a plane, no three co-linear, there is a subset of n of them that form a convex n-gon.

How will you brute-force that?

Can I? I don't know for certain. I said I think I can. Also, there's nothing that says the brute force process can't run forever (presumably it must) but I'd also suspect to generate lots of data while it runs that could indeed be used (by someone else) to write the proof.

Maybe,maybe not. We have generated billions of decimal numbers for PI, and we are not any closer to writing a formal proof deciding if there is a pattern to them or not. Maybe a pattern will unravel once we generate billions of billions of these numbers? We don't know. I guess my point is that brute forcing a problem is unlikely to be useful here.

In base Pi there's a quite a simple pattern.

As a starter, can you write a program to deal with just the very next case? It is currently unknown as to whether a collection of 33 points guarantees a convex 7-gon. If you can prove that, even with a computer program, then you get certainly get a paper out of it, possibly jointly with Ron Graham, and possibly getting an Erdős number of 2.

That would be a start. How would you do that?

I think brute force could be used to prove him wrong (if his conjecture is incorrect). However, it won't be enough to prove correct.

Does anyone know the answer to this in three dimensions? I'm curious how many points it takes to always be able to find a convex tetrahedron.

You'll need to be more careful about what you're asking for, because 4 points in 3D always gives a convex tetrahedron, as there are no non-convex tetrahedra. The convex hull of four points (no three colinear) is a tetrahedron.

if you put all the points in a straight line wouldn't that invalidate any n?

edit: just saw the bit where no more than 3 can be in a straight line

No more than two may be on any line.

I admit I was thinking of a different happy ending.

Reply on news.ycombinator.com