[MDS 1] CAN - Joining of a node

[Teq]

Okay, i'm currently working on Task 3a) of Assignment 3.

If a node joins, it gets a random (x,y) pair, and then routes to the responsible node, which will split its OWN zone in two parts!
In a 2d space, this splitting must always be first X then Y, X, Y ... and so on.
But also, every zone must have a ratio of 1:1, 1:2 or 2:1 according to slide 65.



Okay, first node:
n_1 = (9,11) takes the whole space.
n_2 = (4,4), we split on the x-axis at x = 10, n_2 controls the right part.
n_3 = (17,5), n_2 is responsible, split its area on the y-axis.
n_4 = (8,5), n_1 is responsible, BUT:
Now, on the one hand, i have to split on the x-axis again. But on the other hand, the resulting rectangles would have a ratio of 1:4 ...


If anybody knows how to do it right, i would greatly appreciate your help

[Teq]

Okay, this might be a way to avoid this problem:
(2d)
If you first split on X then you have to split on Y in the next step, respectivly
first Y then X.
However, in the next step you are free again to choose if you want to split on the X or Y-axis.

Well, at least it worked for the Task, however i'm still not sure if that is the correct way

[bla84]

I think you only have to follow this order, if you have a choise:
On slide 67 + 68 you can see, that they split the x-axis twice, too.

So this is probably what you found out, too - just wanted to confirm that.

Good luck tomorrow

[bla84]

other question:

who is responsible for coordinates on borders?
Node 5 (20;10) lies exatcly between the zones of n2 and n3, so who is responsible for it?

[Martin]

who is responsible for coordinates on borders?
Node 5 (20;10) lies exatcly between the zones of n2 and n3, so who is responsible for it?

If I remember correctly, Klaus wasn't sure about this. It's just a question of definition / implementation and shouldn't have any impact on the important issues.

[Teq]

other question:

who is responsible for coordinates on borders?
Node 5 (20;10) lies exatcly between the zones of n2 and n3, so who is responsible for it?

Well,
according to the book from LNCS Series:
If you have a range [0...63] of 64 values that is splitted in 2 zones, you'd use [0...31] for zone 1 and [32...63] for zone 2.


However, in the Assignment we have 21 possible values: [0....20].
I don't think CAN allows a zone from [0...10.4] and one from [10.5 ... 20],
so i would guess it is [0....10] and [11...20].
But this case is not covered in the book, maybe it's a implementational issue..

Edit: Oh, too late. 7 minutes too late, i should type faster

[bla84]

thanks!

now another question just popped up:
I just noticed slide 75, where the x-y-order is next to the partitionig tree.
Is it possible that this indicates the order, of how to split?

in the exercise:
n1: whole zone;
n2: x -> right zone in n1
n3: y -> bottom zone in n2
n4: y , because same level in partitioning tree?
Otherwise this tree would look strange

o
/ \ X
o o
/ \ / \ Y
1 4 2 3

edit: ok, thought the tree would look better...

[Teq]

Hm yeah, this seems to work very well
So you just go to the target node in your tree, and you automatically know how to split..I should have noticed that earlier ^^

[seth]

Let me get some things straight. You are never free to choose on which axis to split. The depth in the partitioning tree determines how to split as bla84 suggested. Now as you noticed there are some problems with assignment 3. According to the CAN paper the coordinates of a joining node simply determines the region which has to be splitted. Not the region it will be responsible for. Not the axis at which to split. So i think a node may be "located" in a region it is not responsible for, but that does not matter at all.

[Teq]

Yeah that is obvious, because it is already happening for node 2. After the splitting, both nodes are in the left region. However, n_2 is in control of the right region, if i'm not mistaken.

[seth]

However, in the next step you are free again to choose if you want to split on the X or Y-axis.

Well, at least it worked for the Task, however i'm still not sure if that is the correct way

However, in the Assignment we have 21 possible values: [0....20].

However, n_2 is in control of the right region, if i'm not mistaken.

Der However-Count dieses Freds ist mir jetzt definitiv zu hoch. Tschüß.