Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBetween Shapes, Using the Hausdorff Distance
114
0
0.0
(
0
)
Added by
Jordi Vermeulen
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given two shapes $A$ and $B$ in the plane with Hausdorff distance $1$, is there a shape $S$ with Hausdorff distance $1/2$ to and from $A$ and $B$? The answer is always yes, and depending on convexity of $A$ and/or $B$, $S$ may be convex, connected, or disconnected. We show that our result can be generalised to give an interpolated shape between $A$ and $B$ for any interpolation variable $alpha$ between $0$ and $1$, and prove that the resulting morph has a bounded rate of change with respect to $alpha$. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.
rate research
Read More
Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size $n$ and $m$, the Hausdorff distance under translation can be computed in time $tilde O(nm)$ for the $L_1$ and $L_infty$ norm [Chew, Kedem SWAT92] and $tilde O(nm (n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of $(nm)^{1-o(1)}$ for $L_1$ and $L_infty$ (and all other $L_p$ norms) assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis.
We study the problem of localizing a configuration of points and planes from the collection of point-to-plane distances. This problem models simultaneous localization and mapping from acoustic echoes as well as the notable structure from sound approach to microphone localization with unknown sources. In our earlier work we proposed computational methods for localization from point-to-plane distances and noted that such localization suffers from various ambiguities beyond the usual rigid body motions; in this paper we provide a complete characterization of uniqueness. We enumerate equivalence classes of configurations which lead to the same distance measurements as a function of the number of planes and points, and algebraically characterize the related transformations in both 2D and 3D. Here we only discuss uniqueness; computational tools and heuristics for practical localization from point-to-plane distances using sound will be addressed in a companion paper.
Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in near-linear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github.
One of the central notions to emerge from the study of persistent homology is that of interleaving distance. It has found recent applications in symplectic and contact geometry, sheaf theory, computational geometry, and phylogenetics. Here we present a general study of this topic. We define interleaving of functors with common codomain as solutions to an extension problem. In order to define interleaving distance in this setting we are led to categorical generalizations of Hausdorff distance, Gromov-Hausdorff distance, and the space of metric spaces. We obtain comparisons with previous notions of interleaving via the study of future equivalences. As an application we recover a definition of shift equivalences of discrete dynamical systems.
This paper studies the properties of a new lower bound for the natural pseudo-distance. The natural pseudo-distance is a dissimilarity measure between shapes, where a shape is viewed as a topological space endowed with a real-valued continuous function. Measuring dissimilarity amounts to minimizing the change in the functions due to the application of homeomorphisms between topological spaces, with respect to the $L_infty$-norm. In order to obtain the lower bound, a suitable metric between size functions, called matching distance, is introduced. It compares size functions by solving an optimal matching problem between countable point sets. The matching distance is shown to be resistant to perturbations, implying that it is always smaller than the natural pseudo-distance. We also prove that the lower bound so obtained is sharp and cannot be improved by any other distance between size functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
