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
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.
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.
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.
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.
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.
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.
18 comments
[ 2.9 ms ] story [ 46.8 ms ] threadThat 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
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.
But I share your enthusiasm - my PhD is in graph theory.
How will you brute-force that?
That would be a start. How would you do that?
edit: just saw the bit where no more than 3 can be in a straight line