zbMATH — the first resource for mathematics

Computing the Hausdorff distance of two sets from their distance functions. (English) Zbl 07309478
In the paper, the author studies the problem of computing the Hausdorff distance between two sets using their distance functions. Throughout the paper, the author assumes that the considered sets are compact sets of an \(n\)-dimensional real space. In the beginning, the author shows a representation of the Hausdorff distance in terms of the distance functions. Then, he considers the situation on a rectangular, bounded grid in \(\mathbb{R}^n\) with uniform spacing \(h\) in each dimension and derives an upper bound on the distance. Using an example, the author shows that the derived estimates are sharp when there are no additional constraints on the involved sets. But when the sets are a little more specific, much better estimates are achieved. In such a case, the approximation error converges quadratically with the grid size. Moreover, the author also shows that even super-quadratic convergence rates can be expected if the orientation of the grid is not related to the two considered sets in two-dimensional space.
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
DLMF; Octave
Full Text: DOI
[1] Delfour, M. C. and Zolésio, J.-P., Shapes and Geometries: Metrics, Analysis, Differential Calculus, and Optimization, (SIAM, 2011), second edition. · Zbl 1251.49001
[2] Huttenlocher, D. P., Klanderman, G. A. and Rucklidge, W. J., Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence15 (1993) 850.
[3] Sim, D.-G., Kwon, O.-K. and Park, R.-H., Object Matching Algorithms Using Robust Hausdorff Distance Measures, IEEE Transactions on Image Processing8 (1999) 425.
[4] Jesorsky, O., Kirchberg, K. J. and Frischholz, R. W., Robust Face Detection Using the Hausdorff Distance, in Proceedings of the Third International Conference on Audio- and Video-based Biometric Person Authentication (Springer, 2001), , pp. 90-95. · Zbl 0987.68966
[5] Schütze, O., Esquivel, X., Lara, A. and Coello, C. A. C., Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization, IEEE Transactions on Evolutionary Computation16 (2012) 504.
[6] Nutanong, S., Jacox, E. H. and Samet, H., An Incremental Hausdorff Distance Calculation Algorithm, in Proceedings of the VLDB Endowment (2011), Vol. 4, pp. 506-517.
[7] M. J. Atallah, A Linear Time Algorithm for the Hausdorff Distance Between Convex Polygons, Computer Science Technical Reports, Paper 363, 1983, http://docs.lib.purdue.edu/cstech/363/. · Zbl 0527.68051
[8] Keuthen, M. and Kraft, D., Shape Optimization of a Breakwater, Inverse Problems in Science and Engineering24 (2016) 936, http://dx.doi.org/10.1080/17415977.2015.1077522. · Zbl 1357.49149
[9] Kraft, D., A Hopf-Lax Formula for the Level-Set Equation and Applications to PDE-Constrained Shape Optimisation, in Proceedings of the 19th International Conference on Methods and Models in Automation and Robotics (IEEE Xplore, 2014), pp. 498-503.
[10] Sethian, J. A., A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proceedings of the National Academy of Sciences93 (1996) 1591. · Zbl 0852.65055
[11] D. Kraft, The level-set Package for GNU Octave, Octave Forge, 2014-2015, http://octave.sourceforge.net/level-set/.
[12] J. W. Eaton, D. Bateman, S. Hauberg and R. Wehbring, GNU Octave version 4.0.0 manual: a high-level interactive language for numerical computations, 2015, https://www.gnu.org/software/octave/doc/interpreter/.
[13] Chenais, D. and Zuazua, E., Finite-Element Approximation of 2D Elliptic Optimal Design, Journal de Mathématiques Pures at Appliquées85 (2006) 225. · Zbl 1086.49027
[14] Ross, S. M., Simulation (Academic Press, 2013), fifth edition. · Zbl 1255.65001
[15] Yeh, J., Real Analysis: Theory of Measure and Integration (World Scientific, 2006), second edition. · Zbl 1098.28002
[16] NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/, Release 1.0.9 of 2014-08-29, online companion to^17
[17] Olver, F. W. J., Lozier, D. W., Boisvert, R. F. and Clark, C. W., eds., NIST Handbook of Mathematical Functions (Cambridge University Press, New York, NY, 2010), print companion to^16 · Zbl 1198.00002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.