Computing the Hausdorff distance of two sets from their distance functions

DOI10.1142/S0218195920500028MaRDI QIDQ5149569zbMATH OpenOpenAlexFDO

Authors Daniel Kraft

Publication date 11 February 2021

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.06740

zbMATH Keywords

distance functionerror estimateHausdorff distance

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The Hausdorff distance is a measure of (dis-)similarity between two sets which is widely used in various applications. Most of the applied literature is devoted to the computation for sets consisting of a finite number of points. This has applications, for instance, in image processing. However, we would like to apply the Hausdorff distance to control and evaluate optimisation methods in level-set based shape optimisation. In this context, the involved sets are not finite point sets but characterised by level-set or signed distance functions. This paper discusses the computation of the Hausdorff distance between two such sets. We recall fundamental properties of the Hausdorff distance, including a characterisation in terms of distance functions. In numerical applications, this result gives at least an exact lower bound on the Hausdorff distance. We also derive an upper bound, and consequently a precise error estimate. By giving an example, we show that our error estimate cannot be further improved for a general situation. On the other hand, we also show that much better accuracy can be expected for non-pathological situations that are more likely to occur in practice. The resulting error estimate can be improved even further if one assumes that the grid is rotated randomly with respect to the involved sets.

Recommendations

• Computing the Hausdorff distance between two sets of parametric curves
• scientific article; zbMATH DE number 2209711
• COMPUTING THE HAUSDORFF DISTANCE BETWEEN CURVED OBJECTS
• Computing the Hausdorff set distance in linear time for any \(L_ p\) point distance
• Minimum Hausdorff distance under rigid motions and comparison of protein structures

Cites work

• A fast marching level set method for monotonically advancing fronts.
• A linear time algorithm for the Hausdorff distance between convex polygons
• Finite-element approximation of 2D elliptic optimal design
• scientific article; zbMATH DE number 1726611 (Why is no real title available?)
• NIST handbook of mathematical functions
• Real analysis. Theory of measure and integration
• Shape optimization of a breakwater
• Shapes and geometries. Metrics, analysis, differential calculus, and optimization
• Simulation.

Cited in

(12)

• Computing the Monge-Kantorovich distance
• On the complexity of computing the Hausdorff distance
• Hausdorff matching and Lipschitz optimization
• Hausdorff distances between distributions using optimal transport and mathematical morphology
• Measure-theoretic properties of level sets of distance functions
• scientific article; zbMATH DE number 524100 (Why is no real title available?)
• Hyperbolic Hausdorff Distance for Medial Axis Transform
• Computation of the Hausdorff distance between two ellipses
• Minimum Hausdorff distance under rigid motions and comparison of protein structures
• The Hausdorff distance between some sets of points
• Hausdorff distance between convex semialgebraic sets
• Computing the Hausdorff set distance in linear time for any \(L_ p\) point distance

Describes a project that uses

Uses Software

• Octave
• DLMF

This page was built for publication: Computing the Hausdorff distance of two sets from their distance functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5149569)