Any hints for this problem will be appreciated.
Little Adam
You have |xi-yj|+|yi-zj|+|zi-xj|. This can be written like
p(i,j) = +(xi - yj) + (yi - zj) + (zi - xj )
p(i,j) = -(xi - yj) + (yi - zj) + (zi - xj )
...
p(i,j) = -(xi - yj) - (yi - zj) - (zi - xj )
For every point you can calculate 16 values.
8 of them if this point is at index i in formula( first value) and
8 of them if this point is at index j in formula( second value).
You can remember only the biggest values for every sign combination ( you must only be careful that the max for signs combination you add don't be for the same point , this way you'll get p(i , i) ).
So the max p(i, j) is the biggest value you get by adding the biggest first value for a sign combination with the biggest second value for the corresponding sign combination.
I hope you get the idea.
p(i,j) = +(xi - yj) + (yi - zj) + (zi - xj )
p(i,j) = -(xi - yj) + (yi - zj) + (zi - xj )
...
p(i,j) = -(xi - yj) - (yi - zj) - (zi - xj )
For every point you can calculate 16 values.
8 of them if this point is at index i in formula( first value) and
8 of them if this point is at index j in formula( second value).
You can remember only the biggest values for every sign combination ( you must only be careful that the max for signs combination you add don't be for the same point , this way you'll get p(i , i) ).
So the max p(i, j) is the biggest value you get by adding the biggest first value for a sign combination with the biggest second value for the corresponding sign combination.
I hope you get the idea.
Thank you very much. I think I understand the idea.
so u calculate
xi+yi+zi
-xi+yi+zi
-xi-yi+zi
...
-xi-yi-zi
...
16 values
and then u get the biggest value for a sign out of all n possibilities?
and then u add the biggest sign value(for instance xi+yi+zi)
with the apropriate sign valuse(in this case -xj-yj-zj)
and then u get the max one from 16 possibilities?
xi+yi+zi
-xi+yi+zi
-xi-yi+zi
...
-xi-yi-zi
...
16 values
and then u get the biggest value for a sign out of all n possibilities?
and then u add the biggest sign value(for instance xi+yi+zi)
with the apropriate sign valuse(in this case -xj-yj-zj)
and then u get the max one from 16 possibilities?
Acctually you have 8 values for x , y ,z , and another 8 for y , z, x because you must take every point as first point in formula ( index i ) and as second point in formula (index j ).
You can only calculate the first 8 of them, but if you do so you can easily find corresponding second state.
If you have +xi - yi + zi then you can add only those who are like -yj + zj - xj.
You can only calculate the first 8 of them, but if you do so you can easily find corresponding second state.
If you have +xi - yi + zi then you can add only those who are like -yj + zj - xj.
ok but there is a problem,for instance the biggest xi+yi+zi=10
xi=1
yi=3
zi=6
and u have -xj-yj-zj=-5
with
xj=1
yj=3
zj=1
u cant just add 10 and -5=5
cause u have
|1-3|=2
|3-1|=2
|6-1|=5
and thats 9 in total not 5 like u would do 10-5
that can happen cause in order to d (xi-yi)+(yi-zj)+(zi-xj) u must have xi>=yj yi>=zj zi>=xj
EDIT:well it seems that it doesnt really matter cause even if u get the wrong result it still wont be the largest one cause then the other sign combinatio(in this case with xi negative and yj positive) will have a bigger value(and the correct one)
EDIT2:well i am not really sure about cases of N>2 and i believe the proof of this method is a lot harder to get then the idea itself and would also like to point out that in case the min distance is required this method would not give correct results
xi=1
yi=3
zi=6
and u have -xj-yj-zj=-5
with
xj=1
yj=3
zj=1
u cant just add 10 and -5=5
cause u have
|1-3|=2
|3-1|=2
|6-1|=5
and thats 9 in total not 5 like u would do 10-5
that can happen cause in order to d (xi-yi)+(yi-zj)+(zi-xj) u must have xi>=yj yi>=zj zi>=xj
EDIT:well it seems that it doesnt really matter cause even if u get the wrong result it still wont be the largest one cause then the other sign combinatio(in this case with xi negative and yj positive) will have a bigger value(and the correct one)
EDIT2:well i am not really sure about cases of N>2 and i believe the proof of this method is a lot harder to get then the idea itself and would also like to point out that in case the min distance is required this method would not give correct results
actually i came up with a proof:D