Distance measures for point sets and their computation
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.
- An algorithm for computing the restriction s|caffold assignment problem in computational biology
- Distribution of distances and triangles in a point set and algorithms for computing the largest common point sets
- Distance measures with heavy aggregation operators
- Exploration of digital-filter and forward-stepwise synthetic turbulence generators and an improvement for their skewness-kurtosis
- A graded approach to database repair by context-aware distance semantics
- A distance function for computing on finite subsets of Euclidean spaces
- Metrics based on average distance between sets
- Fréchet distance between two point sets
- Novel semi-metrics for multivariate change point analysis and anomaly detection
- Scaling and compressing melodies using geometric similarity measures
- Selecting a subset of diverse points based on the squared Euclidean distance
- Efficient many-to-Many point matching in one dimension
- Distance measures for well-distributed sets
- Computing the Monge-Kantorovich distance
- Distances between sets based on set commonality
- Distance semantics for database repair
- Matching point sets with respect to the earth mover's distance
- Distance measures between digital fuzzy objects and their applicability in image processing
- An O(n^2) algorithm for the limited-capacity many-to-many point matching in one dimension
- scientific article; zbMATH DE number 3913720 (Why is no real title available?)
- scientific article; zbMATH DE number 175988 (Why is no real title available?)
- Information-based distance measures and the canonical reflection of view updates
- scientific article; zbMATH DE number 2062646 (Why is no real title available?)
- Curvature based shape detection
- Minimum many-to-many matchings for computing the distance between two sequences
- A new measure between sets of probability distributions with applications to erratic financial behavior
- Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
- Quantitative classification of vortical flows based on topological features using graph matching
- Context-aware distance semantics for inconsistent database systems
- Stochastic distance transform
- Distance between vector-valued fuzzy sets based on intersection decomposition with applications in object detection
- When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
- Fréchet Distance for Uncertain Curves
- scientific article; zbMATH DE number 7758314 (Why is no real title available?)
- Equivalence relations and \(L^p\) distances between time series with application to the black summer Australian bushfires
- Polychotomous kernel Fisher discriminant via top-down induction of binary tree
- Polynomial-Time Algorithms for Continuous Metrics on Atomic Clouds of Unordered Points
- Statistical Modeling and Monitoring of Geometrical Deviations in Complex Shapes With Application to Additive Manufacturing
- Data-driven performance measures using global properties of attractors for testing black-box surrogate models of chaotic systems
- An o(n n)-time approximation scheme for geometric many-to-many matching
- Revisiting the Fréchet distance between piecewise smooth curves
- Constrained many-to-many point matching in two dimensions
- Static and streaming data structures for Fréchet distance queries
- Computational geometric aspects of rhythm, melody, and voice-leading
- Content-based image collection summarization and comparison using self-organizing maps
This page was built for publication: Distance measures for point sets and their computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920226)
