Distance measures for point sets and their computation Export

@article{citeulike:4085784, abstract = {Abstract.\ \ 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 supply 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.}, author = {Eiter, Thomas and Mannila, Heikki}, citeulike-article-id = {4085784}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s002360050075}, citeulike-linkout-1 = {http://www.springerlink.com/content/3hmt90fje7438yyu}, comment = {* The hausdorff distance is a metric * all the other distances are not a metric (violation of triangle inequality)}, day = {16}, doi = {10.1007/s002360050075}, journal = {Acta Informatica}, keywords = {vector-set-distance}, month = {February}, number = {2}, pages = {109--133}, posted-at = {2009-03-05 07:33:12}, priority = {0}, title = {Distance measures for point sets and their computation}, url = {http://dx.doi.org/10.1007/s002360050075}, volume = {34}, year = {1997} }

TY - JOUR ID - citeulike:4085784 L3 - citeulike-article-id:4085784 N2 - Abstract.  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 supply 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. IS - 2 JF - Acta Informatica EP - 133 TI - Distance measures for point sets and their computation VL - 34 SP - 109 KW - vector-set-distance N1 - * The hausdorff distance is a metric * all the other distances are not a metric (violation of triangle inequality) AU - Eiter, Thomas AU - Mannila, Heikki PY - 1997/02/16/ UR - http://dx.doi.org/10.1007/s002360050075 ER -