RANDOM AFFINE ITERATED FUNCTION SYSTEMS - CURVE GENERATION AND WAVELETS

It is shown how refinement methods for smooth curve generation can be carried out efficiently through iterated function systems (IFS). Affine transformations are constructed so that, when composed randomly, they generate the desired smooth curve. Underlying this random algorithm is the "tree traversal" property of IFS. Under a refinement method the points on the curve correspond to leaves on some N-ary tree. IFS theory enables one to generate all of these leaves through a single orbit of an appropriate Markov chain. Applications include Bezier curves, splines, wavelets and various interpolants.