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.

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

GIARLOTTA, Alfio;URSINO P.
2016-01-01

Abstract

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.
2016
Minimum-distance point; Centroid; Steiner center; Manhattan distance
File in questo prodotto:
File Dimensione Formato  
centroid AMS.pdf

solo gestori archivio

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 367.65 kB
Formato Adobe PDF
367.65 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/18110
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact