Cell complexes and digital convexity. (English) Zbl 1052.68785

Bertrand, Gilles (ed.) et al., Digital and image geometry. Advanced lectures. Berlin: Springer (ISBN 3-540-43079-2). Lect. Notes Comput. Sci. 2243, 272-282 (2001).
Summary: Abstract cell complexes (ACC’s) were introduced by Kovalevsky as a means of solving certain connectivity paradoxes in graph-theoretic digital topology, and to this extent provide an improved theoretical basis for image analysis. We argue that ACC’s are a very natural setting for digital convexity, to the extent that their use permits simple, almost trivial formulations of major convexity results such as Caratheodory’s, Helly’s and Radon’s theorems. ACC’s also permit the use in digital geometry of axiomatic combinatorial geometries such as oriented matroids. We give a brief indication of how standard convexity algorithms from computational geometry applied to the points of an ACC can form a substantial part of digital convexity algorithms.
For the entire collection see [Zbl 0984.00020].


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: Link