A graph theoretic formulation of bit pattern algorithms for graphics

✍ Scribed by Satoru Kawai

• Publisher: Elsevier Science
• Year: 1978
• Weight: 968 KB
• Volume: 7
• Category: Article
• ISSN: 0146-664X
• DOI: 10.1016/s0146-664x(78)80015-x

✦ Synopsis

A graph theoretic fm'mulal;ion of bil; patl:ern ttlgm'it,hms fro' computer graphics in presented. A two-dimensiomd N X N bit array, called dm canwts memm'y, in used I;. formubt~e the concept, s of dom~dn, bmmdary (;urve, and semming, which are used to describe basic picture processing ~figm'ithms su(;h as smm (.m~versbn, domain partitioning, inclusion resin, scissoring, and (;ross 1)oinl; deteel, i.n. The basis of l,hc i'(n'muhtLi.n in given in (:erms of poin(~ met,, cycle in dual gr~ph, mul pseudo-Hamilt,(mia, n path. Except for I~he (mmputatiomJ (,ime comI)lexit,y .[sea, n eonversi(m, which is inherently qumh'atie, O(N~), in terms of the res.luthm N, line~u' (O(N)) alg.rit,hms fro' all t,he (~t,hcr basic picl;ure proeessing operati.ns are presen(,ed.