Distance measures for point sets and their computation
type: Item
instance of: scholarly article
title: Distance measures for point sets and their computation
zbMATH Open document ID: 0865.51011
author: Thomas Eiter
author: Heikki Mannila
published in: Acta Informatica
publication date: 1996-09-25T00:00:00Z
review text: We consider the problem of measuring the similarity or distance between two finite sets of points in a metric space, and computing the measure. This problem has applications in, e.g., computational geometry, philosophy of science, updating or changing theories, and machine learning. We review some of the distance functions proposed in the literature, among them the minimum distance link measure, the surjection measure, and the fair surjection measure, and apply polynomial time algorithms for the computation of these measures. Furthermore, we introduce the minimum link measure, a new distance function which is more appealing than the other distance functions mentioned. We also present a polynomial time algorithm for computing this new measure. We further address the issue of defining a metric on point sets. We present the metric infimum method that constructs a metric from any distance functions on point sets. In particular, the metric infimum of the minimum link measure is a quite intuitive. The computation of this measure is shown to be in NP for a broad class of instances; it is NP-hard for a natural problem class.
Mathematics Subject Classification ID: 51K05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 918711
zbMATH Keywords: distances
zbMATH Keywords: point sets
zbMATH Keywords: metrics
zbMATH Keywords: computational complexity
zbMATH Keywords: graph algorithms
zbMATH Keywords: metric space
MaRDI profile type: Publication
full work available at URL: s002360050075
OpenAlex ID: W1993265270
DOI: 10.1007/S002360050075
description: scientific article; zbMATH DE number 918711