2002/01/30 by Jobst Heitzig, Heitzig, Jobst
Business, Management and Accounting · Computer Science · Mathematics · Social Sciences · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geographic Information Systems Studies #Information Systems and Technology Applications #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.math/0201298
Software can be tested at http://www-ifm.math.uni-hannover.de/~heitzig/distance
arxiv created 2002/01/30 · openalex publication_date 2002/01/30 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Different types of two- and three-dimensional representations of a finite metric space are studied that focus on the accurate representation of the linear order among the distances rather than their actual values. Lower and upper bounds for representability probabilities are produced by experiments including random generation, a rubber-band algorithm for accuracy optimization, and automatic proof generation. It is proved that both farthest neighbour representations and cluster tree representations always exist in the plane. Moreover, a measure of order accuracy is introduced, and some lower bound on the possible accuracy is proved using some clustering method and a result on maximal cuts in graphs.