Powers of Circular-Arc Models

FRANCISCO J. SOULIGNAC; PABLO TERLISKY

Lima

Congreso; XIX Congreso Latino-Iberoamericano de Investigación Operativa (XIX CLAIO); 2018

ALIO

A proper circular-arc (PCA) model is a pair M = (C, A) such that C is a circle and A is a finite family of inclusion-free arcs of C. Each arc A of A has two extremes: its beginning point s(A) and its ending point t(A), which are the first and last points of A reached when C is traversed clockwise, respectively. A PCA model is a (c,l)-CA model when the circumference of the circle is c and all arcs of A have length l. Two PCA models are equivalent if the extremes of their arcs appear in the same order when C is traversed clockwise.For any A in A, its next arc is defined as the arc next(A)=A´ such that s(A´) is the last beginning point reached before t(A) when C is traversed clockwise. The emph k-th power of A is defined recursively as A^1=A and A^k=(s(A), t(next(A^{k-1}))), while the k-th power of a model M is M^k = (C,{A^k | A in A}). For a (c,l)-CA model U, we define the j-th multiple of U as jU = (C, {(s(A), s(A)+jl) | A in A}).In this work we study the question of whether some model M is k-multiplicative, i.e., determining if the models M^i and iM are equivalent for all i at most k. In order to solve this problem, we adapt the results Soulignac and Terlisky recently provided in "Integrality of circular-arc models" and generalize them.