Computing the minimum distance between each pain of points
-
29-09-2020 - |
Question
I am trying to read an algorithm for computing minimum distance between each pair of points from the book: Algorithm Design
It considers the points in a line. If the points are in a line why we need to sort them? We can start from the beginning and compute the distances from starting pint to all the points on the right.
Some body please guide me why we need sorting?
Solution
Suppose the points are $[4,1,10,11]$. The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points.
In this problem, the input is an array containing numbers, not in sorted order.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange