euclidean_manhantan_chebyshev.txt (5455B)
1 =============================================================================== 2 Manhattan (L1), Euclidean (L2), Chebyshev (L-inf) 3 =============================================================================== 4 5 Distance metrics: different answers to "how far apart are two points?" 6 All three are special cases of the Minkowski distance 7 8 D_p(a, b) = ( sum_i |a_i - b_i|^p )^(1/p) 9 10 with p = 2, p = 1, p = infinity. They all satisfy the metric axioms 11 (non-negative, zero iff identical, symmetric, triangle inequality), so 12 any of them is a valid metric for k-NN, clustering, or A* -- they just 13 disagree about what "close" means. 14 15 16 MANHATTAN (L1, taxicab, city block) 17 ------------------------------------ 18 d = sum_i |a_i - b_i| 19 2D: |dx| + |dy| 20 21 Distance walking a street grid: you may only move along axes. 22 23 - Unit ball is a diamond (rotated square). 24 - NOT rotation-invariant -- rotating the frame changes distances. 25 - Grows linearly with each difference, so outliers are penalized less 26 than under L2; more robust. 27 - No sqrt, no multiplication -> cheap, exact in integers. 28 - The natural L1 "center" is the coordinate-wise median, not the mean. 29 - In high dimensions it discriminates better than L2, which suffers 30 more from distance concentration (all points look equidistant). 31 32 Use when: 4-way grid movement (up/down/left/right, no diagonals), 33 circuit routing, warehouse/robot paths, lasso-style sparsity, and as the 34 admissible A* heuristic on a 4-connected grid. 35 36 37 EUCLIDEAN (L2, p = 2) 38 ---------------------- 39 d = sqrt( sum_i (a_i - b_i)^2 ) 40 2D: sqrt(dx^2 + dy^2) 41 42 Straight-line "as the crow flies" distance. The one everyone means by 43 default. 44 45 - Rotation-invariant: the only one of the three that is. Rotating the 46 coordinate frame doesn't change distances. 47 - Unit ball is a circle / sphere. 48 - Smooth and differentiable away from zero -> gradient descent likes it. 49 - Squares the differences, so large deviations dominate; sensitive to 50 outliers. 51 - Costs a sqrt. For ranking/comparison, use squared distance instead -- 52 monotonic, so it gives the same ordering, and it's exact in integers. 53 54 Use when: real physical space, free movement in any direction, least 55 squares, k-means (whose mean-as-centroid step assumes L2). 56 57 58 CHEBYSHEV (L-inf, chessboard) 59 ------------------------------ 60 d = max_i |a_i - b_i| 61 2D: max(|dx|, |dy|) 62 63 Only the single largest coordinate difference counts -- the others come 64 along free. 65 66 - Unit ball is an axis-aligned square / cube. 67 - Number of king moves on a chessboard: a king covers one step in x 68 and one in y simultaneously, so the diagonal is free. 69 - Also the right model for a machine whose axes move in parallel at 70 equal speed (a CNC/plotter's travel time is the slowest axis). 71 - Cheapest of the three to compute. 72 73 Use when: 8-way grid movement with uniform cost, tolerance checks 74 ("every component within eps"), max-error bounds, A* heuristic on an 75 8-connected grid. 76 77 78 COMPARISON 79 ---------- 80 Take dx = 3, dy = 4: 81 82 Euclidean sqrt(9 + 16) = 5 83 Manhattan 3 + 4 = 7 84 Chebyshev max(3, 4) = 4 85 86 Ordering always holds (in n dimensions): 87 88 L-inf <= L2 <= L1 <= n * L-inf 89 90 so Chebyshev is the loosest bound and Manhattan the tightest -- which is 91 exactly why the choice of A* heuristic matters: all three are admissible 92 on a free-movement grid, but the largest admissible one expands the 93 fewest nodes. 94 95 Euclidean Manhattan Chebyshev 96 unit ball circle diamond square 97 rotation-inv. yes no no 98 cost sqrt adds max 99 outliers sensitive robust only max matters 100 center statistic mean median midrange 101 grid movement any angle 4-way 8-way 102 diagonal step sqrt(2) 2 1 103 104 Relations worth knowing: 105 - In 2D, rotating 45° and scaling maps L1 <-> L-inf: 106 (x, y) -> (x + y, x - y) turns Manhattan distance into Chebyshev. 107 Handy for turning diagonal-movement problems into axis-aligned ones. 108 - Diagonal / octile distance is the honest 8-way grid metric when a 109 diagonal step costs sqrt(2) instead of 1: 110 d = (dx + dy) + (sqrt(2) - 2) * min(dx, dy) 111 It sits between Chebyshev and Manhattan; use it, not Chebyshev, when 112 diagonals aren't free. 113 - As p -> infinity the Minkowski ball inflates from a diamond (p=1) to 114 a circle (p=2) to a square (p=inf). p < 1 is not a metric -- it 115 violates the triangle inequality. 116 117 118 PICKING ONE 119 ----------- 120 Movement is unconstrained and physical -> Euclidean 121 Movement is axis-locked / grid, no diagonal -> Manhattan 122 Diagonals cost the same as straight steps -> Chebyshev 123 Diagonals cost sqrt(2) -> octile 124 High-dimensional feature vectors -> Manhattan often better 125 Outliers in the data -> Manhattan 126 You only need an ordering, not a value -> squared Euclidean 127 128 129 HOW THIS RELATES TO COORDINATE SYSTEMS 130 -------------------------------------- 131 See cartesian_polar_spehrical.txt. Coordinate systems change how a point 132 is *named*; metrics change how far apart two points *are*. The two 133 interact: L2 is the only one of these metrics invariant to the choice of 134 (rotated) Cartesian frame, which is why polar/spherical conversions 135 preserve Euclidean distance but scramble Manhattan and Chebyshev.