AN OPTIMAL PARALLEL ALGORITHM FOR DIGITAL CURVE SEGMENTATION

First we give an optimal EREW PRAM algorithm that finds an unknown dis crete monotone function f, with domain and range of size n, in O(log n ) time using O(n) independent threshold queries of kind ''f(x) greater than or equal to y?''. Here ''independent'' means that simultaneous q ueries always refer to mutually disjoint values x and y. This is used for solving, within the same resources, a certain segmentation problem for words over semigroups. The classical problem of partitioning a di gital curve into a minimum number of digital line segments, which is o f interest in digital image processing, turns out to be a special case of this, and can therefore be solved in O(log n) time using O(n) work on an EREW PRAM. This strengthens and generalizes all known algorithm ic results about digital curve segmentation. As a further prerequisite we use the Dorst-Smeulders parametrization of digital line segments.