A family of algorithms for generating discrete embeddings of continuous objects

C.W.A.M. Overveld, van

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationTheoretical foundations of computer graphics and CAD
EditorsR.A. Earnshaw
Place of PublicationBerlin
Number of pages11
ISBN (Electronic)978-3-642-83539-1
ISBN (Print)978-3-642-83541-4
Publication statusPublished - 1988

Publication series

NameNATO ASI Series, Series F: Computer and Systems Sciences
ISSN (Print)1387-6694


Dive into the research topics of 'A family of algorithms for generating discrete embeddings of continuous objects'. Together they form a unique fingerprint.

Cite this