an algorithm to compute the convex hull in the plane from the distance matrix
There exist a variety of algorithms for the convex hull problem in the plane. The input to all of these is the set of points in terms of their coordinates. In this short note, a convex hull algorithm is presented in which the points are specified not through their coordinates but in terms of the distances between pairs of them in the form of a distance matrix. Some applications where this is the case are mentioned, and the algorithm's performance is analyzed and shown to be O(n 2 ) in the worst case.
convex hull distance matrix computational geometry design of algorithms