6533b862fe1ef96bd12c7789

RESEARCH PRODUCT

Approximate convex hull of affine iterated function system attractors

Sandrine LanquetinDmitry SokolovAnton MishkinisChristian Gentil

subject

Discrete mathematicsConvex hull0209 industrial biotechnologyGeneral MathematicsApplied Mathematics010102 general mathematicsProper convex functionConvex setMathematicsofComputing_GENERALGeneral Physics and AstronomyStatistical and Nonlinear Physics02 engineering and technology[ INFO.INFO-GR ] Computer Science [cs]/Graphics [cs.GR]01 natural sciences[INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR]020901 industrial engineering & automationAffine hullTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYConvex polytopeOutput-sensitive algorithmConvex combination0101 mathematicsConvex conjugateMathematics

description

International audience; In this paper, we present an algorithm to construct an approximate convex hull of the attractors of an affine iterated function system (IFS). We construct a sequence of convex hull approximations for any required precision using the self-similarity property of the attractor in order to optimize calculations. Due to the affine properties of IFS transformations, the number of points considered in the construction is reduced. The time complexity of our algorithm is a linear function of the number of iterations and the number of points in the output convex hull. The number of iterations and the execution time increases logarithmically with increasing accuracy. In addition, we introduce a method to simplify the approximation of the convex hull without loss of accuracy.

yearjournalcountryeditionlanguage
2012-11-01
https://hal.inria.fr/hal-00755842/document