A family of algorithms for generating discrete embeddings of continuous objects

A substantial part of algorithms both in raster graphics and in scene analysis can be considered to deal with the problem: given a set L , L ⊂ R n , find the set Emb(L ) with: Emb(L)={x ∊ bold Z sup n |:(E l ∊ L :dist(x,l)≤ 1)}. Here dist(x,l ) stands for the distance between x and l. and n is the dimension of the space we are interested in. Using the technique of invariants [1], by means of which algorithms are derived mathematically from their specifications. we construct an algorithm for generating Emb(L) for an arbitrary, finite and connected L. The complexity of this algorithm is, worst case, O(nlogn) in the number of elements n of Emb(L ). The internal memory requirements are an order of magnitude less than n, and the algorithm is well suited for vectorization. Algorithms, similar to the one in this paper, have been applied in the field of pattern recognition (propagation labeling-or dilation algorithms [2]). In that case, L represents some spatial object from the real world. We will focus on what we believe to be new applications in the domain of rastergraphics. Here L is the mathematical definition of the object to be rasterized. We illustrate the algorithm with some examples.