Topological properties of Hausdorff discretization, and comparison to other discretization schemes

AbstractWe study a new framework for the discretization of closed sets and operators based on Hausdorff metric: a Hausdorff discretization of an n-dimensional Euclidean figure F of Rn, in the discrete space Dρ=ρZn, is a subset S of Dρ whose Hausdorff distance to F is minimal (ρ can be considered as the resolution of the discrete space Dρ); in particular such a discretization depends on the choice of a metric on Rn. This paper is a continuation of our works (Ronse and Tajine, J. Math. Imaging Vision 12 (3) (2000) 219; Hausdorff discretization for cellular distances, and its relation to cover and supercover discretization (to be revised for JVCIR), 2000, Wagner et al., An Approach to Discretization Based on the Hausdorff Metric. I. ISMM’98, Kluwer Academic Publishers, Dordrecht, 1998, pp. 67–74), in which we have studied some properties of Hausdorff discretizations of compact sets.In this paper, we study the properties of Hausdorff discretization for metrics induced by a norm and we refine this study for the class of homogeneous metrics. We prove that for such metrics the popular covering discretizations are Hausdorff discretizations. We also compare the Hausdorff discretization with the Bresenham discretization (Bresenham, IBM Systems J. 4 (1) (1965) 25). Actually, we prove that the Bresenham discretization of a straight line of R2 is not always a good discretization relatively to the Hausdorff metric. This result is an extension of Tajine et al. (Hausdorff Discretization and its Comparison with other Discretization Schemes, DGCI’99, Paris, Lecture Notes in Computer Sciences Vol. 1568, Springer, Berlin, 1999, pp. 399–410), in which we prove the same result for a segment of R2. Finally, we study how some topological properties of the Euclidean plane R2 are translated in discrete space for Hausdorff discretizations. Actually, we prove that a Hausdorff discretization of a connected closed set is 8-connected and its maximal Hausdorff discretization is 4-connected for homogeneous metrics