On recursive, O(N) partitioning of a digitized curve into digital straight segments
M. Linderbaum, Alfred Marcel Bruckstein · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1993
A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O(N) time and O(1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers.>