A customer needs the nearest warehouse, but “nearest” needs a distance rule. Euclidean distance measures the straight-line distance between two points. It is useful when their coordinates reasonably represent the space in which closeness matters. section 8.2.3 section 8.3
For points with coordinates (x₁, …, xₖ) and (y₁, …, yₖ), compute the square root of the sum of squared coordinate differences: √Σ(xᵢ − yᵢ)². In one dimension, this reduces to the absolute difference between positions. The coordinates can describe other attributes, such as price and rating, when a distance over those dimensions is appropriate. section 8.2.3 section 8.3
Start with warehouses on one road
Put every warehouse and customer on a straight line, measured from an origin. To find the nearest warehouse to position 75, a linear scan can compare every stored position. If the positions are ordered, binary search narrows the candidates; once only 62 and 80 remain, compare their distances to 75 and choose 80. This simpler model avoids the geometry of a two-dimensional map. section 8.2.3
That straight road is an approximation, not a universal model of travel. A two-dimensional map simplifies locations on Earth’s curved surface, while straight-line distance also ignores the roads a delivery must follow. Choose the model to match the precision the task requires. section 8.2.3 section 14.5.1
The same distance idea has different algorithmic jobs:
- In nearest-neighbor search, compare a target with stored points to retrieve the closest point, the closest N points, or points within a distance-defined region. section 8.3
- In an SS-tree, compare a point’s distance from a node’s centroid with the node’s radius to decide whether that node could contain the point. Here Euclidean distance is one option; another valid metric can be used. section 10.3.1
- In A* route search, use straight-line distance to the destination as a heuristic when road distance is the path cost. Because a road route cannot be shorter than the straight line, the estimate is optimistic. section 14.5.1
For the one-dimensional ordered case, binary search avoids checking every position. In higher dimensions, the choice of search structure and distance measure matters; the straight-line calculation alone does not specify how to search a collection efficiently. section 8.2.3 section 8.3
