Hausdorff discretization for cellular distances and its relation to cover and supercover discretizations
This paper is a sequel to (C. Ronse and M. Tajine, 2000, J. Math. Imaging Vision 12, 2000, 219-242), where we introduced a new type of discretization. Let E be a Euclidean space and D a discrete subset of E: in practice, one usually takes epsilon = R-N and D = Z(n). Given a compact subset K of E, we call a Hausdorff discretizing set of K any finite subset S of D, whose Hausdorff distance to K is minimal; there is always a greatest Hausdorff discretizing set, which we call the maximal Hausdorff discretization of K. We gave a mathematical characterization of these sets. Here we consider the relation between this new discretization and those based on the intersection of the Euclidean set with the cells (pixels or voxels) corresponding to the discrete points. Of particular interest are what we call cellular distances, that is those for which every Euclidean point in a discrete point's cell is closer to that point than to any other one; for such a distance, the supercover discretization [6] made of all discrete points whose cell intersects the compact set, and the cover discretizations of Andres [1] are Hausdorff discretizing sets; conversely, the supercover is a Hausdorff discretizing set only for cellular distances. Except in some special cases where the discrete space is unhomogeneous, the supercover is the maximal Hausdorff discretization iff the distance is cellular and the cells are all the closed (or open) balls of cellular covering radius; e.g. in the usual case of square cells in R-n, this happens only for the chessboard distance (up to a constant factor), (C) 2001 Academic Press.
hausdorff compact sets cellular and regular distances supercover and cover discretizations