Questions confound me like a song stuck in your head. Luckily, there's a great way to forget them.
A friend of mine had been interviewing recently, and he related an interesting interview question to me. At the time, I bumbled my way through it, and we were all talking about angles and affine systems and all sorts of crap. Armed with a white-board, however, it’s embarrassingly easy (unless I misinterpreted or misremembered the question). The question is thus:
There are a series of points on a random plane. Each point is connected to the point nearest to it. In this world, is it possible to create a polygon? Also, is it possible for two lines to cross?
The answer to the first question, of course, is yes. If the dots are arranged in a grid, because each adjacent point is equidistant, either all of those points will be connected by lines, or they will be chosen by some rule. If the rule is random or I get to choose, then somewhere on the grid you’re going to see a square. However, this isn’t fun so let’s assume that there’s always a closer or further away alternative.
The answer to the second question is “depends”. Depends on whether two lines joining counts as two lines “crossing”. If it does, then it’s clear to see that if you only have three points on this plane, there will be a join somewhere.
For the first question, I’m going to do a proof by contradiction. Imagine there’s a polygon in this space. Then you have four points: A, B, C, and D. You have four lines for each of the points and their nearest neighbour: a, b, c, and d (obviously, a connects AB, b connects BC, etc. because they make a polygon). now, we choose one of these to be the longest edge, in this case “a”. Then, len(b) < len(a); len© < len(b); len(d) < len©, and, to join back up, len(a) < len(d). However, a is the longest edge! Contradiction! You can follow this logic for any number of edges, or you could do induction.
For the second question, I’m going to use the same trick. Imagine there’s a crossed line somewhere. You have edges A, B, C, D, and lines a(AC) and b(BD). We don’t really care about any other lines, except that a and b cross at some point. now let’s cleft the lines in twain; a1 on one side of the cross, and a2 on the other, and b1 and b2 similarly. now imagine edges x(AB), and y(CD). len(x) < len(a1+b1), and len(y) < len(a2+b2). You probably have to draw this to make it make sense, and switch a1/a2, and b1/b2 around until it makes sense. Anyhoo, len(x+y) < len(a1+b1+a2+b2) = len(a+b). That is, either x or y is shorter than a or b. Contradiction!
So umm... yeah... affine transforms my arse (Full disclosure: I was the one who said affine transform).