4 ms·
The conversion from the given metric to the 'taxicab' metric needs some justification! Else use just the n^2 approach or, if really want to struggle for someth
by NY_Entrepreneur 15y ago
The conversion from the given metric to the 'taxicab' metric needs some justification!
Else use just the n^2 approach or, if really want to struggle for something faster, then use my convexity approach.
There may be another approach if can find a cute way to exploit the special properties of that special metric.
- anonymoushn 15y agoThe taxicab metric is useful here because if you compute the components of a distance in the square metric, you must max() them together, while under the taxicab metric you can add them together. We can add a pair of large sums together to get the large sum of pairs, but we can't max() a pair of large sums together to get the large sum of max()es. One way to get to the taxicab metric verson of the problem is to take w = x + y and z = x - y. From then on all the distances you calculate in wz-space under the taxicab metric will be precisely twice the distance between the same points in xy-space under the square metric.
- NY_Entrepreneur 15y agoNice! Then, if all this is correct, your solution should be nicely fast. Cute conversion of the metrics!