Article ID: | iaor201113537 |
Volume: | 38 |
Issue: | 1 |
Start Page Number: | 5 |
End Page Number: | 23 |
Publication Date: | Jan 2004 |
Journal: | Algorithmica |
Authors: | Eckhardt Ulrich, Reiter Helene |
Keywords: | computational geometry, decomposition, evolutionary algorithms, geometry, graphical methods |
In the context of discrete curve evolution the following problem is of relevance: decompose the boundary of a plane digital object into convex and concave parts. Such a decomposition is very useful for describing the form of an object, e.g. for shape databases. Although the problem is relatively trivial in ordinary plane geometry, in digital geometry its statement becomes a very difficult task due to the fact that in digital geometry there is no simple set‐complement duality. The paper is based on results given by Hübler et al. The main new contribution of the paper is the generalization of the concepts introduced by these authors to nonconvex sets. The digital geometric ‘low level’ segmentation of the boundary of a digital object can be used as a starting basis for further reduction of the boundary by means of discrete evolution.