4 ms·
The Happy Ending Problem [video]
- deleted 12y ago[deleted]
- ilzmastr 12y agoReminds 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/scribe_notes/0221.pdf https://www.cs.princeton.edu/courses/archive/spring13/cos511... Wonder if the 2^(n-2) + 1 rule is somewhere in the VC dim lit
- agentultra 12y agoI 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.
- ColinWright 12y agoThis 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.
- agentultra 12y agoRight, it's a geometrical problem... my suggestion is a bit of a tangent.
- delinka 12y agoI 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...
- ColinWright 12y agoSo 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?
- delinka 12y agoCan 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.
- gambiting 12y agoMaybe,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.
- peterkelly 12y agoIn base Pi there's a quite a simple pattern.
- ColinWright 12y agoAs 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?
- willvarfar 12y agoIt 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.
- dec0dedab0de 12y agoif 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
- willvarfar 12y agoNo more than two may be on any line.
- zackmorris 12y agoDoes 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.
- ColinWright 12y agoYou'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.
- ivancamilov 12y agoI admit I was thinking of a different happy ending.