An Optimal Algorithm for the Straight Segment Approximation of Digital Arcs

✍ Scribed by Y.M. Sharaiha; N. Christofides

• Publisher: Elsevier Science
• Year: 1993
• Weight: 842 KB
• Volume: 55
• Category: Article
• ISSN: 1049-9652
• DOI: 10.1006/cgip.1993.1030

✦ Synopsis

In this paper, we define the straight segment approximation problem (SSAP) for a given digital arc as that of locating a minimum subset of vertices on the arc such that they form a connected sequence of digital straight segments. Sharaiha (Ph.D. thesis, Imperial College, London, 1991) introduced the compact chord property, and proved its equivalence to Rosenfeld's chord property (IEEE Trans. Comput. C-23, 1974, 1264-1269). The SSAP is now constrained by the compact chord property, which offers a more convenient geometric representation than the chord property. We develop an (O\left(n^{2}\right)) optimal algorithm for the solution of the SSAP using integer arithmetic. A relaxation of the problem is also presented such that the optimal number of vectors can be reduced according to a user definition. The original algorithm is adapted for the optimal solution of the relaxed problem. An extension to the relaxed problem is also addressed which finds a minimum level of relaxation such that the optimal number of vectors cannot be reduced. 01993 Academic Press. Inc.