Some Remarks on an Efficient Algorithm to Find a Centroid in a k-Dimensional Real Space

Given a finite configuration of points in a metric space, a Steiner center (respectively, a centroid) is the point of the space (respectively, of the configuration) that minimizes the sum of the distances from all its elements. Working on the k-dimensional real space endowed with the Manhattan distance, we study the approximate algorithm that takes a point of minimum distance from the Steiner center of a configuration as its centroid. This algorithm is more efficient than all known approximate algorithms to obtain a centroid, and has applications in bio-informatics and economics, where data bases are quite large. Experimental results show that both the magnitude and the frequency of the error drastically decrease as the configuration becomes very large. We determine upper bounds to the magnitude of the error as a difference and as a ratio, and provide arguments to justify the negligible frequency of the error for large configurations.