Short Circuit's Journal: Multidimensional triangulation software

I wrote a PHP script that narrows down the field of a search as you feed it data points, and threw it up on Google Code under the GPLv2. You can try it here.

Here's a description of the algorithm I devised for it:

We determine the region the target lies in by creating the smallest-possible n-sphere guaranteed to contain all of the points contained in the overlapping region between two other n-spheres. While this necessarily returns an n-volume larger than really necessary, we're guaranteed that our target is within the region, and our calculation is simplified.

On each iteration of the algorithm, we intersect the newest data point with the previous estimated region, and the smallest n-sphere containing that intersection becomes our new estimated region.

Unless someone else already has a patent on it, I consider my algorithm to be in the public domain.

Prior art

[benhocking]

I haven't looked at your actual algorithm, but what you describe sounds like the problem of finding "convex hulls in more than two dimensions", which is a section in chapter 3 of Preparata and Shamos's book "Computational geometry: an introduction". OTOH, they don't mention a patent, either, so having your code is still a good thing. Thanks for your contributions!

Re:

[Short Circuit]

No problem...

My brother wanted support software to aid him in finding resources in a game called Eve Online. This was what I came up with.

I'm kinda proud of it, as by simplifying the problem, I simplified the computation requirements. I only have to store 1+n values between data inputs, where n is the number of dimensions. The way I wrote the code, you can even work in one dimension, and find the overlap in line segments. (Which I think is kinda cool, if, for example, you wanted to find the most accurate