Start making a latice by picking a point to be the root...

Now pick another point and make it a child...

The general rule for adding another point is:

For a parent G with children {A,B,...} and a point k to be sorted, there are 4 things that can happen, in order of precedence:

1. k is closer to the midpoint of G and and one or more X,Y... of {A,B,...}; than the midpoint is to either G or X

or

2. k is closer to G than it is to any X of {A,B,...}

or

3. k is closer to the midpoint of two of G's children, X and Y, than it is to either of the children in question

or

4. k is closest to one of the children X

and what you do for each case is:

1. remove X,Y... and any of their children from the tree and replace with k

2. add k as a child to G

3. take X and Y as parent nodes and repeat the process placing k somewhere under both

4. restart the process starting with X as the parent node

So for the example given:

1. k is not closer to the midpoint of G and E than either G or E

2. k is closer to G than it is to E

so we do 2 and make k another child of G

Now considering point b, we get all the way to rule 4, and make the new parent node E and continue with rule 2 adding b as a child of E.

Now considering point d, we would need rule 3 and make d a child of both e and k... Sometimes you will have to write it in the tree as two nodes but here we can draw it as one with 2 parents easily...

In the end you end up with a lattice where every node is closest to one of it's parents or one of it's children...

** To be added**

I'll write some source code and post some results with big maps...
## No comments:

## Post a Comment