## 4.25.2010

### Traveling Salesman, continued.

Inbetween fighting with my OS's and discovering the wonders of Playonlinux, and my wondrous library of old games I can play again, I suppose I really should get back to this; It's kinda important.

Here I have a diagram of one case that might pop up while you're messing with Geometric Collapse. This is (supposed to be) a grid of points arranged all nice and neat for your convenience. (I blame MSPaint for my horrible art skills)

We do our normal Geometric Collapse first step, wrapping a rubber band around the outer points, and take a look at the closest point - problem is, that's all of them. Choosing one at random to begin, we see that there are two points on the path that are the closest to the new point, this causes much confusion.

Not to worry, we can just take things in order. When you have the choice of which point to hit up next, just take things in stride, and things will work out.

We can't add the point to the path a second time, that's... well, bad. But whatever. In case you're wondering, the point to the left there is now the nearest neighbor and will be connected to the diagonal line now. You'll end up with an H shape, if you follow along correctly.

But now we're going to break Geometric Collapse.

Here's a picture of a path that defeats the algorithm, depending on how you look at it.

It's very easy to see where the outer path will be once you've started, but then you have an interesting conundrum like the one above. You'll start out like that H pattern, creating a square indention in the path, but then you have a very strange problem. The nearest neighbor (well, had I drawn it more appropriately) will actually be very close to dead-even with a path directly outward from the nearest point. This is tricky because If Geometric Collapse worked correctly, we (sorta) know that we'd end up with a large C shape in the end. But I'm not too confident that will actually happen.

Will our hero turn out triumphant in the end? Who knows. Ooh, shiny!

Let's turn our attention (deficit disorder) to a new method: Geometric Explosion.

Geometric Explosion is much like Geometric Collapse in practice, with you building a path from points in space, but the coolest part of Geometric Explosion is that it works in 2d, 3d, and even 4d space (with Time as the 4th dimension).

This time, instead of creating a path around the outer edge and working our way in, we're going to create something out of nothing, beginning with a very simple geometric feature and 'exploding' it outward until it becomes an incredibly complex and beautiful path, which in the end will connect back to its real start and form a loop.

We begin with a cluster of stars, out in space.

No pictures here, since I'm bad enough at 2-dimensional artwork.

What we do first is create an imaginary point in space at the center of gravity/mass of that star cluster.

Then we draw a dotted line from that point to its nearest neighbor. This is our 'starting' point but we haven't even really begun in real space yet, we have an imaginary line and a real point in space.

From there we find the nearest neighbor to the imaginary path, and connect the real point to that point with a real line.

Now at this point I have to stop you because I find this very cool even though it's completely trivial information. We've just created a sort of triangle, only it's a triangle with one side of length ci, where c is a constant and i is the infamous imaginary number, the square root of -1. Our second side is of length c2, a second constant. our third side is of length NaN, or not a number, null, etc. We've effectively just linked together the real, the imaginary, and the nonexistent, and proven that the three are distinctly different. Sweet! I shall hereby dub thee the 'Awesome Triangle!" I'm sure plenty of math professors out there will consider you a waste of time but that, in my opinion, is the best way to use time. Back to the shortest path we go...

From here on we proceed much in the same way as we would with Geometric Collapse, with a nearest-neighbor-to-the-path procession through our stars, which will eventually form a large snake through space, and once all the stars are covered, we simply connect the tail to the head and form our Ouroboros. (Score another point for video game vocabulary!)

But what if those stars are actually moving?

Surely space is not so boring. Well, whatever. In the case of stars it's very easy to calculate what their path will be over the estimated time of your star trek, so we just use that as a guideline. We can give each star a curved vector to describe its path through space, and that gives us a timeline for each star. That means that the first star along the path will be connected to the "earliest" part of its vector, and the last star will be connected to the "latest" part of its vector. Something we might want to keep in mind is what might happen if a star decides "screw this I'm going bowling" and goes nova as we're along that path, all of the stars are going to have their vectors dramatically changed, but we can just roll with it. After all, we're able to calculate this path out so fast that we can do it while we're on the way to the first star. Let's just hope our shields can handle it, Captain.

As was the case before, I welcome any and all commentary on my methods, and encourage you to offer feedback. If you see anything wrong, take a torch to the house of cards and help build a better one! If this does turn out to stand up to scrutiny, that's a wonderful thing because it calls into question the idea that P is not equal to NP. If it fails your tests, that's just as important to know.

Best of luck to you all as you attempt to prove or disprove the theories, and have fun.

Subscribe to:
Posts (Atom)