text: IEEE TRANSACTIONS ON SIGNAL PROCESSING 3 (cid:98) (cid:34) { } (cid:88) (cid:104) (cid:105) which intuitively treats yi as noisy o(cid:98){bse}rv(cid:98)ations(cid:98)of a func- where tion g indexed by x, sampled at points x . Let g = g(x ), an estimate of the function value, w{ith }g =i (g1 . . . ign)(cid:62), ani d F2(yi, xi, zi, g, A, B) =∆ E m G∗(yj) + G(a(cid:62)j xi(cid:35)+ b(cid:62)j zi) x denote the jth element of the x sorted in ascending [j] i j=1 order. Then LMR is described by the problem, (cid:88) − (cid:62) (cid:98) y (Axi + Bzi) . (14) (cid:0) n (cid:1) (cid:0)− (cid:1) g =∆ LMR(y, x) = argmin (g(x ) y )2 i i Now consider the case in which the true distribution remains s.t. 0 ≤g g xi=1 −g x ≤ x −x (10) the same, but we only observe xi a(cid:34)n(cid:88)d n(cid:104)ot zi, (cid:105) [j+1] [j]− [j+1] [j] (cid:98) (cid:98) for j = 1, . . . , n 1. (g, A) =argmin F (y , x , g, A) =∆ E m G∗(y ) + G(cid:35)(a(cid:62)x ) While there may (cid:98)be in fact inﬁnitely man(cid:98)y possible (con- g,A 3 i i ji j i j=1 tinuous) monotonic increasing Lipschitz functions g that pass − (cid:62) through the points g, the solution vector g is unique. We yi (Axi) will introduce a simple yet effective algorithm for solving(cid:98)this ∇ ∈ C problem later in Section . s.t. g = G 1. (15) We now return to the objective function (8). Let g = (cid:62) LMR(y, X a). Then the gradient w.r.t. a can be expressed We now propose a relation between the two models in (13) in terms of an estimate of g without explicit computation of and (15), which will ﬁnally lead to the SILVar model. Here we G or G∗, (cid:88) present the abridged theore(cid:98)m, and relegate the full expressions (cid:98) and derivation to Appendix . To establish notation, let primes ( ∇ n − (cid:48)) denote derivatives, hats ( ) denote a parameter estimate with F = [(g y ) x ] . (11) a 1 i i i only observed variables, overbars ( ) denote an underlying i=1 parameter estimate when we have access to both observed and This allows us to apply gradient or quasi-Newton methods to latent variables, and we drop the subscripts from the random solve the minimization in a, which is itself a convex problem variables x and z to reduce (cid:98)clutter. (cid:98) since the original problem was jointly convex in g and a. (cid:48) (cid:0) (cid:54) | (cid:48)(cid:48)|(cid:1)≤ Theo|re(cid:48)(cid:48)m| ≤1. Assume that g (0)∞(cid:98)= 0 and that g J and g(cid:0) J for some J < (cid:107) . (cid:107)Fur(cid:107)ther(cid:107)more(cid:107), a(cid:1)s(cid:107)sum≤e in models (14) and (15) that max a , a + b k, III. SINGLE INDEX LATENT VARIABLE MODELS j j 1 j 1 j 2 max E[(cid:107)x(cid:107) (cid:107)x(cid:107)2∞], E[(cid:107)x(cid:107) (cid:107)x(cid:107)∞(cid:107)z(cid:107) ], E[(cid:107)x(cid:107) (cid:107)z(cid:107)2] ≤ s , In this section, we build the Single Index Latent Variable 2 2 2 2 2 (cid:98)Nr (SILVar) model from fundamental concepts. where subscripts in s indicate that the bounds may grow Nr with the values in the subscript. Then, the parameters A and (cid:98) A. Multitask regression and latent variables A from models (14) and (15) are related as First, we extend the SIM to the multivariate case and A = q(A + L) + E, tthheenlienxeaamr ipnaerahmoewterl.a(cid:62)tLenett yvairia=ble(sy1cian. . .afyfemcit)(cid:62)(cid:62)le,argn(ixng) o=f where q = gg(cid:98)(cid:16)(cid:48)(cid:48)((00)), µx = E[xi], (cid:98) (cid:17) (cid:0) (cid:1) (g1(x1) . . . gm(xm)) , and A = (cid:0)(a1 . .(cid:1). am) . Consider E (cid:62) − (cid:62) E (cid:62) † the vectorization, L = B [zx ] + (g(0) g(0)) µx [xx ] ⇒ (cid:98) ≤ E | (cid:62) rank(L) r + 1, [y x ] = g a x ⇒ E [yji|xi] = gj(Axj )i. (12) and E = A − q(A + L) is bound√ed as i i i (cid:98) For the remainder of this paper, we make an assumption that (cid:13)(cid:13)(cid:13)(cid:0)M1(cid:2)N (cid:107)E(cid:107)(cid:3)(cid:1)F (cid:13)(cid:13)(cid:13)≤ 2gJ(cid:48)(σ0(cid:96))MN sNrk2, all g = g for notational simplicity, though the same analysis j E (cid:62) † readily extends to the case where g are distinct. where σ = xx , the largest singular value of the Now, let us introduce a set of jlatent variables z ∈ Rr pseudo-i(cid:96)nverse of the covar2iance. (cid:28) i with r p and the corresponding linear parameter B = (cid:62) ∈ R × The proof is given in Appendix . The assumptions require (b . . . b ) m r (note we can incorporate a linear offset 1 m ← (cid:62) (cid:62) that the 2nd order Taylor series expansion is accurate around by augmenting the variable z (z 1) and adding the linear off(cid:0)set as a c(cid:1)olumn of B). This leads to the asymptotic the point 0, that the model parameters A and B are bounded, and that the distributions generating the data are not too spread maximum likelihood estimate, out (beyond 0 where the Taylor series expansion is perfo(cid:98)rmed). These are all intuitively reasonable and unsurprising assump- g, A, B = argmin F2 (yi, xi, zi, g, A, B) | (cid:48)(cid:48)| g,A,B (13) tions. Though the theorem poses a hard constraint on g , we ∇ ∈ C s.t. g = G 1, hypothesize that this is a rather strong condition that can be weakened to be in line with similar models. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: IEEE

text: TRANSACTIONS

text: ON

text: SIGNAL

text: PROCESSING

text: which

text: intuitively

text: treats

text: yi

text: as

text: noisy

text: a

text: func-

text: where

text: tion

text: g

text: indexed

text: by

text: x,

text: sampled

text: at

text: points

text: x

text: Let

text: g

text: g(x

text: an

text: estimate

text: of

text: the

text: function

text: value,

text: w{ith

text: }g

text: =i

text: ani

text: d

text: xi,

text: zi,

text: g,

text: A,

text: B)

text: E

text: m

text: G∗(yj)

text: zi)

text: x

text: denote

text: the

text: jth

text: element

text: of

text: the

text: x

text: sorted

text: in

text: ascending

text: [j]

text: i

text: order.

text: Then

text: LMR

text: is

text: described

text: by

text: the

text: problem,

text: y

text: (Axi

text: Bzi)

text: n

text: g

text: LMR(y,

text: x)

text: argmin

text: (g(x

text: y

text: i

text: i

text: Now

text: consider

text: the

text: case

text: in

text: which

text: the

text: true

text: distribution

text: remains

text: s.t.

text: ≤g

text: g

text: −g

text: x

text: x

text: −x

text: the

text: same,

text: but

text: we

text: only

text: observe

text: xi

text: zi,

text: [j]−

text: [j]

text: for

text: j

text: n

text: (g,

text: A)

text: =argmin

text: F

text: (y

text: x

text: g,

text: A)

text: E

text: m

text: G∗(y

text: While

text: there

text: may

text: in

text: fact

text: inﬁnitely

text: possible

text: (con-

text: g,A

text: i

text: i

text: ji

text: j

text: i

text: tinuous)

text: monotonic

text: increasing

text: Lipschitz

text: functions

text: g

text: that

text: pass

text: through

text: the

text: points

text: g,

text: the

text: solution

text: vector

text: g

text: is

text: unique.

text: We

text: yi

text: (Axi)

text: will

text: introduce

text: a

text: simple

text: yet

text: effective

text: algorithm

text: for

text: C

text: problem

text: later

text: in

text: Section

text: s.t.

text: g

text: G

text: We

text: now

text: return

text: to

text: the

text: objective

text: function

text: Let

text: g

text: LMR(y,

text: X

text: a).

text: Then

text: the

text: gradient

text: w.r.t.

text: a

text: can

text: be

text: expressed

text: We

text: now

text: propose

text: a

text: relation

text: between

text: the

text: two

text: models

text: in

text: in

text: terms

text: of

text: an

text: estimate

text: of

text: g

text: without

text: explicit

text: computation

text: of

text: and

text: which

text: will

text: ﬁnally

text: lead

text: to

text: the

text: SILVar

text: model.

text: Here

text: we

text: G

text: or

text: G∗,

text: present

text: the

text: abridged

text: and

text: relegate

text: the

text: full

text: expressions

text: and

text: derivation

text: to

text: Appendix

text: To

text: establish

text: notation,

text: let

text: primes

text: n

text: denote

text: derivatives,

text: hats

text: denote

text: a

text: parameter

text: estimate

text: with

text: F

text: [(g

text: y

text: x

text: a

text: i

text: i

text: i

text: only

text: observed

text: variables,

text: overbars

text: denote

text: an

text: underlying

text: parameter

text: estimate

text: when

text: we

text: have

text: access

text: to

text: both

text: observed

text: and

text: This

text: allows

text: us

text: to

text: apply

text: gradient

text: or

text: quasi-Newton

text: methods

text: to

text: latent

text: variables,

text: and

text: we

text: drop

text: the

text: subscripts

text: from

text: the

text: random

text: solve

text: the

text: minimization

text: in

text: a,

text: which

text: is

text: itself

text: a

text: convex

text: problem

text: variables

text: x

text: and

text: z

text: to

text: reduce

text: since

text: the

text: original

text: problem

text: was

text: jointly

text: convex

text: in

text: g

text: and

text: a.

text: Assume

text: that

text: g

text: and

text: that

text: g

text: J

text: and

text: J

text: for

text: some

text: J

text: in

text: models

text: and

text: that

text: max

text: a

text: a

text: b

text: k,

text: III.

text: SINGLE

text: INDEX

text: LATENT

text: VARIABLE

text: MODELS

text: j

text: j

text: j

text: j

text: max

text: s

text: In

text: this

text: section,

text: we

text: build

text: the

text: Single

text: Index

text: Latent

text: Variable

text: (SILVar)

text: model

text: from

text: fundamental

text: concepts.

text: where

text: subscripts

text: in

text: s

text: indicate

text: that

text: the

text: bounds

text: may

text: grow

text: Nr

text: with

text: the

text: values

text: in

text: the

text: subscript.

text: Then,

text: the

text: parameters

text: A

text: and

text: A.

text: Multitask

text: regression

text: and

text: latent

text: variables

text: A

text: from

text: models

text: and

text: are

text: related

text: as

text: First,

text: we

text: extend

text: the

text: SIM

text: to

text: the

text: multivariate

text: case

text: and

text: A

text: q(A

text: L)

text: E,

text: tthheenlienxeaamr

text: o=f

text: where

text: q

text: µx

text: E[xi],

text: gm(xm))

text: and

text: A

text: am)

text: Consider

text: E

text: E

text: the

text: vectorization,

text: L

text: B

text: [zx

text: µx

text: [xx

text: E

text: rank(L)

text: r

text: [y

text: x

text: g

text: a

text: x

text: E

text: [yji|xi]

text: gj(Axj

text: )i.

text: and

text: E

text: A

text: q(A

text: L)

text: is

text: bound√ed

text: as

text: i

text: i

text: i

text: For

text: the

text: remainder

text: of

text: this

text: paper,

text: we

text: make

text: an

text: assumption

text: that

text: all

text: g

text: g

text: for

text: notational

text: simplicity,

text: though

text: the

text: same

text: analysis

text: j

text: E

text: readily

text: extends

text: to

text: the

text: case

text: where

text: g

text: are

text: distinct.

text: where

text: σ

text: xx

text: the

text: largest

text: singular

text: value

text: of

text: the

text: Now,

text: let

text: us

text: introduce

text: a

text: set

text: of

text: jlatent

text: variables

text: z

text: Rr

text: of

text: the

text: i

text: with

text: r

text: p

text: and

text: the

text: corresponding

text: linear

text: parameter

text: B

text: R

text: The

text: proof

text: is

text: given

text: in

text: Appendix

text: The

text: assumptions

text: require

text: (b

text: b

text: m

text: r

text: (note

text: we

text: can

text: incorporate

text: a

text: linear

text: offset

text: m

text: that

text: the

text: order

text: Taylor

text: series

text: expansion

text: is

text: accurate

text: around

text: by

text: augmenting

text: the

text: variable

text: z

text: (z

text: and

text: adding

text: the

text: linear

text: as

text: a

text: of

text: B).

text: This

text: leads

text: to

text: the

text: asymptotic

text: the

text: point

text: that

text: the

text: model

text: parameters

text: A

text: and

text: B

text: are

text: bounded,

text: and

text: that

text: the

text: distributions

text: generating

text: the

text: data

text: are

text: not

text: too

text: spread

text: maximum

text: likelihood

text: estimate,

text: out

text: (beyond

text: where

text: the

text: Taylor

text: series

text: expansion

text: is

text: These

text: are

text: all

text: intuitively

text: reasonable

text: and

text: unsurprising

text: assump-

text: g,

text: A,

text: B

text: argmin

text: (yi,

text: xi,

text: zi,

text: g,

text: A,

text: B)

text: g,A,B

text: tions.

text: Though

text: the

text: theorem

text: poses

text: a

text: hard

text: constraint

text: on

text: g

text: we

text: C

text: s.t.

text: g

text: G

text: hypothesize

text: that

text: this

text: is

text: a

text: rather

text: strong

text: condition

text: that

text: can

text: be

text: weakened

text: to

text: be

text: in

text: line

text: with

text: similar

text: models.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: IEEE TRANSACTIONS ON SIGNAL PROCESSING 10 1.9 Prediction Errors 50 Estimated link function GLM SILVar 40 1.8 30 1.7 20 10 1.650 100 150 200 250 300 350 400 0-10 0 10 20 30 40 50 Number of Training Samples (n) θ (a) (b) Fig. 4: (a) Root mean squared errors (RMSEs) from SILVar and Oracle models; (b) Link function learned using SILVar model (a) Weather graph learned using SILVar ROC for classifying business day 1 rank 1 0.8 rank 2 rank 3 rank 4 0.6 rank 5 rank 6 0.4 full 0.2 0 0 0.2 0.4 0.6 0.8 1 (b) Weather graph learned using Sp. SIM (without low-rank) False Alarm Rate Fig. 3: Learned weather stations graphs Fig. 5: Receiver operating characte(cid:98)ristics (ROCs) for classify- ing each day as a business day or non-business day, using the low-rank embedding provided by L learned from the SILVar model and using the full data days. We consider the task of using the total number of rides departing from and arriving in each location at 6:00AM- sample sizes, averaged across the 10 trials. We see that the 11:00AM to predict the number of rides departing from each SILVar model outperforms the GLM model by learning the location during the peak period of 11:00AM-2:00PM for each ∈ N × ∈ N × link function in addition to the sparse and low-rank regression day. ThNis corresponds to Y 500 489 and X 1000 489∈, matrices. Figure 4b shows an example of the link function wRhe×re 0 is the set of non-negative integers, and A, L learned by the SILVar model with n = 360 training samples. 50 100. We estimate the SILVar model (16) and compare Note that the learned SILVar link function performs non- its performance against a sparse plus low-rank GLM model negative clipping of the output, which is consisten(cid:98)t with the with an underlying Poisson distribution and ﬁxed link function ∈ { } count-valued nature of the data. gGLM(x) = l(cid:8)og(1 +(cid:12) ex). We use n 60,(cid:9)120, 240, 360 We also test the hypothesis that the learned L contains training samples and(cid:12) compute errors on validation and test information about whether a day is business or non-business sets of size 48 each, and learn the model on a grid of through its relativ(cid:98)ely lo(cid:98)w(cid:98)-d(cid:98)imensional effects on the data. ∈ ∈ {− − } (λS, λL) 10i/4 i 8, 7, . . . , 11, 12 2. We repeat We perform the singular value decompos(cid:101)ition ((cid:98)SV(cid:98)D) on the this 10 times for each setting, using an independent set of (cid:62) optimally(cid:101)learned L = UΣV for n = 360 and project the training samples each time. We compute testing errors in these (cid:62) data onto the r top singular components X = Σ V X. We cases for the optimal (λS, λL) with lowest validation errors for then use X to train a linear support vectorr machriner (SVM) both SILVar and GLM models. r to classify each day as either a business day or a non-business We also demonstrate that the low-rank component of the day, and compare the performance of this lower dimensional estimated SILVar model captures something intrinsic to the feature to th(cid:101)at of using the full vector X to train a linear SVM. data. Naturally, we expect people’s behavior and thus trafﬁc If our hypothesis is true then the performance(cid:101)of the classiﬁer to be different on business days and on non-business days. trained on X should be competitive with that of the classiﬁer r A standard pre-processing step would be to segment the data trained on X. We use 50 training samples of X and of X and r along this line and learn two(cid:98)different models. However, as we test on the remainder of the data. We repeat this 50 times by use the full dataset to learn one single model, we hypothesize drawing a new batch of 50 samples each time. We then vary that the learned low-rank L captures some aspects of this the proportion of business to non-business days in the traini(cid:101)ng underlying behavior. sample to trace out a receiver operating characteristic (ROC). Figure 4a shows the test Root Mean Squared Errors (RM- In Figure 5, we see the results of training linear SVM on X ∈ { } r SEs) for both SILVar and GLM models for varying training for r 1, ..., 6 and on the full data for classifying business ESMR etaR noitceteD )θ(bg ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: IEEE

label: paragraph

text: TRANSACTIONS

text: ON

text: SIGNAL

text: PROCESSING

font: default

text: Prediction

text: Errors

text: Estimated

text: link

text: function

text: GLM

text: SILVar

text: Number

text: of

text: Training

text: Samples

text: (n)

text: θ

text: (a)

text: (b)

text: Fig.

text: (a)

label: caption

text: Root

text: mean

text: squared

text: errors

text: (RMSEs)

text: from

text: SILVar

text: and

text: Oracle

text: models;

text: (b)

text: Link

text: function

text: learned

text: using

text: SILVar

text: model

text: (a)

text: Weather

text: graph

text: learned

text: using

text: SILVar

text: ROC

text: for

text: classifying

text: business

text: day

text: rank

text: rank

text: rank

text: rank

text: rank

text: rank

text: full

text: (b)

text: Weather

text: graph

text: learned

text: using

text: Sp.

text: SIM

text: (without

text: low-rank)

text: False

text: Alarm

text: Rate

text: Fig.

text: Learned

text: weather

text: stations

text: graphs

text: Fig.

text: Receiver

text: operating

text: (ROCs)

text: for

text: classify-

text: ing

text: each

text: day

text: as

text: a

text: business

text: day

text: or

text: non-business

text: day,

text: using

text: the

text: low-rank

text: embedding

text: provided

text: by

text: L

text: learned

text: from

text: the

text: SILVar

text: model

text: and

text: using

text: the

text: full

text: data

text: days.

text: We

text: consider

text: the

text: task

text: of

text: using

text: the

text: total

text: number

text: of

text: rides

text: departing

text: from

text: and

text: arriving

text: in

text: each

text: location

text: at

text: sample

text: sizes,

text: averaged

text: across

text: the

text: trials.

text: We

text: see

text: that

text: the

text: to

text: predict

text: the

text: number

text: of

text: rides

text: departing

text: from

text: each

text: SILVar

text: model

text: outperforms

text: the

text: GLM

text: model

text: by

text: learning

text: the

text: location

text: during

text: the

text: peak

text: period

text: of

text: for

text: each

text: N

text: N

text: link

text: function

text: in

text: addition

text: to

text: the

text: sparse

text: and

text: low-rank

text: regression

text: day.

text: ThNis

text: corresponds

text: to

text: Y

text: and

text: X

text: matrices.

text: Figure

text: shows

text: an

text: example

text: of

text: the

text: link

text: function

text: wRhe×re

text: is

text: the

text: set

text: of

text: non-negative

text: integers,

text: and

text: A,

text: L

text: learned

text: by

text: the

text: SILVar

text: model

text: with

text: n

text: training

text: samples.

text: We

text: estimate

text: the

text: SILVar

text: model

text: and

text: compare

text: Note

text: that

text: the

text: learned

text: SILVar

text: link

text: function

text: performs

text: non-

text: its

text: performance

text: against

text: a

text: sparse

text: plus

text: low-rank

text: GLM

text: model

text: negative

text: clipping

text: of

text: the

text: output,

text: which

text: is

text: with

text: the

text: with

text: an

text: underlying

text: Poisson

text: distribution

text: and

text: ﬁxed

text: link

text: function

text: count-valued

text: nature

text: of

text: the

text: data.

text: gGLM(x)

text: ex).

text: We

text: use

text: n

text: We

text: also

text: test

text: the

text: hypothesis

text: that

text: the

text: learned

text: L

text: contains

text: training

text: samples

text: compute

text: errors

text: on

text: validation

text: and

text: test

text: information

text: about

text: whether

text: a

text: day

text: is

text: business

text: or

text: non-business

text: sets

text: of

text: size

text: each,

text: and

text: learn

text: the

text: model

text: on

text: a

text: grid

text: of

text: through

text: its

text: effects

text: on

text: the

text: data.

text: (λS,

text: λL)

text: i

text: We

text: repeat

text: We

text: perform

text: the

text: singular

text: value

text: on

text: the

text: this

text: times

text: for

text: each

text: setting,

text: using

text: an

text: independent

text: set

text: of

text: L

text: UΣV

text: for

text: n

text: and

text: project

text: the

text: training

text: samples

text: each

text: time.

text: We

text: compute

text: testing

text: errors

text: in

text: these

text: data

text: onto

text: the

text: r

text: top

text: singular

text: components

text: X

text: Σ

text: V

text: X.

text: We

text: cases

text: for

text: the

text: optimal

text: (λS,

text: λL)

text: with

text: lowest

text: validation

text: errors

text: for

text: then

text: use

text: X

text: to

text: train

text: a

text: linear

text: support

text: vectorr

text: machriner

text: (SVM)

text: both

text: SILVar

text: and

text: GLM

text: models.

text: r

text: to

text: classify

text: each

text: day

text: as

text: either

text: a

text: business

text: day

text: or

text: a

text: non-business

text: We

text: also

text: demonstrate

text: that

text: the

text: low-rank

text: component

text: of

text: the

text: day,

text: and

text: compare

text: the

text: performance

text: of

text: this

text: lower

text: dimensional

text: estimated

text: SILVar

text: model

text: captures

text: something

text: intrinsic

text: to

text: the

text: feature

text: to

text: of

text: using

text: the

text: full

text: vector

text: X

text: to

text: train

text: a

text: linear

text: SVM.

text: data.

text: Naturally,

text: we

text: expect

text: people’s

text: behavior

text: and

text: thus

text: trafﬁc

text: If

text: our

text: hypothesis

text: is

text: true

text: then

text: the

text: the

text: classiﬁer

text: to

text: be

text: different

text: on

text: business

text: days

text: and

text: on

text: non-business

text: days.

text: trained

text: on

text: X

text: should

text: be

text: competitive

text: with

text: that

text: of

text: the

text: classiﬁer

text: r

text: A

text: standard

text: pre-processing

text: step

text: would

text: be

text: to

text: segment

text: the

text: data

text: trained

text: on

text: X.

text: We

text: use

text: training

text: samples

text: of

text: X

text: and

text: of

text: X

text: and

text: r

text: along

text: this

text: line

text: and

text: learn

text: models.

text: However,

text: as

text: we

text: test

text: on

text: the

text: remainder

text: of

text: the

text: data.

text: We

text: repeat

text: this

text: times

text: by

text: use

text: the

text: full

text: dataset

text: to

text: learn

text: one

text: single

text: model,

text: we

text: hypothesize

text: drawing

text: a

text: new

text: batch

text: of

text: samples

text: each

text: time.

text: We

text: then

text: vary

text: that

text: the

text: learned

text: low-rank

text: L

text: captures

text: some

text: aspects

text: of

text: this

text: the

text: proportion

text: of

text: business

text: to

text: non-business

text: days

text: in

text: the

text: underlying

text: behavior.

text: sample

text: to

text: trace

text: out

text: a

text: receiver

text: operating

text: characteristic

text: (ROC).

text: Figure

text: shows

text: the

text: test

text: Root

text: Mean

text: Squared

text: Errors

text: (RM-

text: In

text: Figure

text: we

text: see

text: the

text: results

text: of

text: training

text: linear

text: SVM

text: on

text: X

text: r

text: SEs)

text: for

text: both

text: SILVar

text: and

text: GLM

text: models

text: for

text: varying

text: training

text: for

text: r

text: and

text: on

text: the

text: full

text: data

text: for

text: classifying

text: business

text: ESMR

text: etaR

text: noitceteD

text: )θ(bg

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: If randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that there are enough particles. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n2) rounds and moves: this number of moves is also asymptotically optimal. 1 Introduction 1.1 Background The term programmable matter, introduced by Toﬀoli and Margolus over a quarter century ago [26], is used to denote matter that has the ability to change its physical properties (e.g., shape, color, density, etc.) in a pro- grammable fashion, based upon user input or autonomous sensing. Often programmable matter is envisioned as a very large number of very small locally interacting computational particles, programmed to collectively per- form a complex task. Such particles could have applications in a variety of important situations: they could be employed to create smart materi- als, used for autonomous monitoring and repair, be instrumental in minimal invasive surgery, etc. As recent advances in microfabrication and cellular engineering render the production of such particles increasingly possible, there has been a con- vergence of theoretical research interests on programmable matter from some areas of computer science, especially robotics, sensor networks, molecular self-assembly, and distributed computing. Several theoretical models of pro- grammable matter have been proposed, ranging from DNA self-assembly systems (e.g., [8, 17, 18, 20, 21, 24]) to shape-changing synthetic molecules and cells (e.g., [28]), from metamorphic robots (e.g., [4, 27]) to nature- inspired synthetic insects and micro-organisms (e.g., [12, 13, 16]), each model assigning special capabilities and constraints to the entities and focusing on speciﬁc applications. Of particular interest, from the distributed computing viewpoint, is the geometric Amoebot model of programmable matter [3, 6, 7, 9, 10, 11, 12]. In this model, introduced in [12] and so called because inspired by the behav- 2

text: If

label: abstract

text: randomization

text: is

text: allowed,

text: then

text: any

text: input

text: shape

text: can

text: be

text: formed

text: from

text: any

text: initial

text: (simply

text: connected)

text: shape

text: by

text: our

text: algorithm,

text: provided

text: that

text: there

text: are

text: enough

text: particles.

text: Our

text: algorithm

text: works

text: without

text: chirality,

text: proving

text: that

text: chirality

text: is

text: computationally

text: irrelevant

text: for

text: shape

text: formation.

text: Furthermore,

text: it

text: works

text: under

text: a

text: strong

text: adversarial

text: scheduler,

text: not

text: necessarily

text: sequential.

text: We

text: also

text: consider

text: the

text: complexity

text: of

text: shape

text: formation

text: both

text: in

text: terms

text: of

text: the

text: number

text: of

text: rounds

text: and

text: the

text: total

text: number

text: of

text: moves

text: performed

text: by

text: the

text: particles

text: executing

text: a

text: universal

text: shape

text: formation

text: algorithm.

text: We

text: prove

text: that

text: our

text: solution

text: has

text: a

text: complexity

text: of

text: rounds

text: and

text: moves:

text: this

text: number

text: of

text: moves

text: is

text: also

text: asymptotically

text: optimal.

text: Introduction

text: Background

text: The

text: term

text: programmable

text: matter,

text: introduced

text: by

text: Toﬀoli

text: and

text: Margolus

text: over

text: a

text: quarter

text: century

text: ago

text: is

text: used

text: to

text: denote

text: matter

text: that

text: has

text: the

text: ability

text: to

text: change

text: its

text: physical

text: properties

text: (e.g.,

text: shape,

text: color,

text: density,

text: etc.)

text: in

text: a

text: pro-

text: grammable

text: fashion,

text: based

text: upon

text: user

text: input

text: or

text: autonomous

text: sensing.

text: Often

text: programmable

text: matter

text: is

text: envisioned

text: as

text: a

text: very

text: large

text: number

text: of

text: very

text: small

text: locally

text: interacting

text: computational

text: particles,

text: programmed

text: to

text: collectively

text: per-

text: form

text: a

text: complex

text: task.

text: Such

text: particles

text: could

text: have

text: applications

text: in

text: a

text: variety

text: of

text: important

text: situations:

text: they

text: could

text: be

text: employed

text: to

text: create

text: smart

text: materi-

text: als,

text: used

text: for

text: autonomous

text: monitoring

text: and

text: repair,

text: be

text: instrumental

text: in

text: minimal

text: invasive

text: surgery,

text: etc.

text: As

text: recent

text: advances

text: in

text: microfabrication

text: and

text: cellular

text: engineering

text: render

text: the

text: production

text: of

text: such

text: particles

text: increasingly

text: possible,

text: there

text: has

text: been

text: a

text: con-

text: vergence

text: of

text: theoretical

text: research

text: interests

text: on

text: programmable

text: matter

text: from

text: some

text: areas

text: of

text: computer

text: science,

text: especially

text: robotics,

text: sensor

text: networks,

text: molecular

text: self-assembly,

text: and

text: distributed

text: computing.

text: Several

text: theoretical

text: models

text: of

text: pro-

text: grammable

text: matter

text: have

text: been

text: proposed,

text: ranging

text: from

text: DNA

text: self-assembly

text: systems

text: (e.g.,

text: to

text: shape-changing

text: synthetic

text: molecules

text: and

text: cells

text: (e.g.,

text: from

text: metamorphic

text: robots

text: (e.g.,

text: to

text: nature-

text: inspired

text: synthetic

text: insects

text: and

text: micro-organisms

text: (e.g.,

text: each

text: model

text: assigning

text: special

text: capabilities

text: and

text: constraints

text: to

text: the

text: entities

text: and

text: focusing

text: on

text: speciﬁc

text: applications.

text: Of

text: particular

text: interest,

text: from

text: the

text: distributed

text: computing

text: viewpoint,

text: is

text: the

text: geometric

text: Amoebot

text: model

text: of

text: programmable

text: matter

text: In

text: this

text: model,

text: introduced

text: in

text: and

text: so

text: called

text: because

text: inspired

text: by

text: the

text: behav-


text: vertex as a polygonal chain with no edges). Since S(cid:48) is simply connected, the abstract graph obtained by collapsing each maximal polygon of S(cid:48) into a single vertex forms a tree, which has at least one leaf. The leaf may represent the endpoint of a polygonal chain of S(cid:48), which is the location of a 1-corner particle of P (cid:48). Otherwise, the leaf represents a polygon S(cid:48)(cid:48) ⊆ S(cid:48), perhaps connected to the rest of S(cid:48) by a polygonal chain with an endpoint in a vertex v of S(cid:48)(cid:48). Since S(cid:48)(cid:48) is a polygon, it has at least three convex vertices, at most one of which is v. Each other convex vertices of S(cid:48)(cid:48) is therefore the location of a 2-corner particle or a 3-corner particle of P (cid:48). Lemma 5. If a system of contracted Eligible particles forms a simply con- nected shape, and any set of non-locked corner particles is removed at once, the new system forms again a simply connected shape.4 Proof. Instead of removing all the particles in the given set C at once, we remove them one by one in any order, and use induction to prove our lemma. Let P be a system of contracted Eligible particles forming a simply connected shape, and let C(cid:48) be a set of corner particles of P such that, if a particle of C(cid:48) is locked, then its companion is not in C(cid:48). This condition is obviously satisﬁed by the given set C, because it does not contain locked corner particles at all. Let p ∈ C(cid:48), and let P (cid:48) = P \ {p}. We have to prove that P (cid:48) forms a simply connected shape, that C(cid:48) \ {p} is a set of corner particles of P (cid:48), and that C(cid:48) \ {p} does not contain any pair of companion locked particles of P (cid:48). Note that the fact that P (cid:48) forms a simply connected shape is evident, since p is a corner particle of P . Therefore, any path in the subgraph of the grid G induced by P that goes through p may be re-routed through the neighbors of p in P . Now, if C(cid:48) = {p}, there is nothing else to prove. So, let p(cid:48) (cid:54)= p be another particle of C(cid:48). Suppose ﬁrst that p(cid:48) is adjacent to p. Hence, removing p reduces the number of Eligible neighbors of p(cid:48) by one. The only case in which p(cid:48) could cease to be a corner particle would be if p were its middle neighbor, implying that p and p(cid:48) would be locked companions. But this is not possible, because by assumption C(cid:48) does not contain a pair of locked companion particles. Therefore, p(cid:48) is necessarily a corner particle of P (cid:48). Note that p(cid:48) cannot be a 3-corner particle of P (cid:48), because one of its Eligible neighbors (namely, p) has been removed. Hence p(cid:48) cannot be locked in P (cid:48). 4For convenience, with a little abuse of terminology, we treat single vertices of G and D the empty set as shapes, even if technically they are not, according to the deﬁnitions of Section . 19 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: vertex

text: as

text: a

text: polygonal

text: chain

text: with

text: no

text: edges).

text: Since

text: is

text: simply

text: connected,

text: the

text: abstract

text: graph

text: obtained

text: by

text: collapsing

text: each

text: maximal

text: polygon

text: of

text: into

text: a

text: single

text: vertex

text: forms

text: a

text: tree,

text: which

text: has

text: at

text: least

text: one

text: leaf.

text: The

text: leaf

text: may

text: represent

text: the

text: endpoint

text: of

text: a

text: polygonal

text: chain

text: of

text: which

text: is

text: the

text: location

text: of

text: a

text: particle

text: of

text: P

text: Otherwise,

text: the

text: leaf

text: represents

text: a

text: polygon

text: perhaps

text: connected

text: to

text: the

text: rest

text: of

text: by

text: a

text: polygonal

text: chain

text: with

text: an

text: endpoint

text: in

text: a

text: vertex

text: v

text: of

text: Since

text: is

text: a

text: polygon,

text: it

text: has

text: at

text: least

text: three

text: convex

text: vertices,

text: at

text: most

text: one

text: of

text: which

text: is

text: v.

text: Each

text: other

text: convex

text: vertices

text: of

text: is

text: therefore

text: the

text: location

text: of

text: a

text: particle

text: or

text: a

text: particle

text: of

text: P

text: Lemma

text: If

text: a

text: system

text: of

text: contracted

text: Eligible

text: particles

text: forms

text: a

text: simply

text: con-

text: nected

text: shape,

text: and

text: any

text: set

text: of

text: non-locked

text: corner

text: particles

text: is

text: removed

text: at

text: once,

text: the

text: new

text: system

text: forms

text: again

text: a

text: simply

text: connected

text: Proof.

text: Instead

text: of

text: removing

text: all

text: the

text: particles

text: in

text: the

text: given

text: set

text: C

text: at

text: once,

text: we

text: remove

text: them

text: one

text: by

text: one

text: in

text: any

text: order,

text: and

text: use

text: induction

text: to

text: prove

text: our

text: lemma.

text: Let

text: P

text: be

text: a

text: system

text: of

text: contracted

text: Eligible

text: particles

text: forming

text: a

text: simply

text: connected

text: shape,

text: and

text: let

text: be

text: a

text: set

text: of

text: corner

text: particles

text: of

text: P

text: such

text: that,

text: if

text: a

text: particle

text: of

text: is

text: locked,

text: then

text: its

text: companion

text: is

text: not

text: in

text: This

text: condition

text: is

text: obviously

text: satisﬁed

text: by

text: the

text: given

text: set

text: C,

text: because

text: it

text: does

text: not

text: contain

text: locked

text: corner

text: particles

text: at

text: all.

text: Let

text: p

text: and

text: let

text: P

text: P

text: {p}.

text: We

text: have

text: to

text: prove

text: that

text: P

text: forms

text: a

text: simply

text: connected

text: shape,

text: that

text: {p}

text: is

text: a

text: set

text: of

text: corner

text: particles

text: of

text: P

text: and

text: that

text: {p}

text: does

text: not

text: contain

text: any

text: pair

text: of

text: companion

text: locked

text: particles

text: of

text: P

text: Note

text: that

text: the

text: fact

text: that

text: P

text: forms

text: a

text: simply

text: connected

text: shape

text: is

text: evident,

text: since

text: p

text: is

text: a

text: corner

text: particle

text: of

text: P

text: Therefore,

text: any

text: path

text: in

text: the

text: subgraph

text: of

text: the

text: grid

text: G

text: induced

text: by

text: P

text: that

text: goes

text: through

text: p

text: may

text: be

text: re-routed

text: through

text: the

text: neighbors

text: of

text: p

text: in

text: P

text: Now,

text: if

text: {p},

text: there

text: is

text: nothing

text: else

text: to

text: prove.

text: So,

text: let

text: p

text: be

text: another

text: particle

text: of

text: Suppose

text: ﬁrst

text: that

text: is

text: adjacent

text: to

text: p.

text: Hence,

text: removing

text: p

text: reduces

text: the

text: number

text: of

text: Eligible

text: neighbors

text: of

text: by

text: one.

text: The

text: only

text: case

text: in

text: which

text: could

text: cease

text: to

text: be

text: a

text: corner

text: particle

text: would

text: be

text: if

text: p

text: were

text: its

text: middle

text: neighbor,

text: implying

text: that

text: p

text: and

text: would

text: be

text: locked

text: companions.

text: But

text: this

text: is

text: not

text: possible,

text: because

text: by

text: assumption

text: does

text: not

text: contain

text: a

text: pair

text: of

text: locked

text: companion

text: particles.

text: Therefore,

text: is

text: necessarily

text: a

text: corner

text: particle

text: of

text: P

text: Note

text: that

text: cannot

text: be

text: a

text: particle

text: of

text: P

text: because

text: one

text: of

text: its

text: Eligible

text: neighbors

text: (namely,

text: p)

text: has

text: been

text: removed.

text: Hence

text: cannot

text: be

text: locked

text: in

text: P

text: convenience,

text: with

text: a

text: little

text: abuse

text: of

text: terminology,

text: we

text: treat

text: single

text: vertices

text: of

text: G

text: and

text: D

text: the

text: empty

text: set

text: as

text: shapes,

text: even

text: if

text: technically

text: they

text: are

text: not,

text: according

text: to

text: the

text: deﬁnitions

text: of

text: Section

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ior of amoeba, programmable matter is viewed as a swarm of decentralized autonomous self-organizing entities, operating on a hexagonal tessellation of the plane. These entities, called particles, are constrained by having sim- ple computational capabilities (they are ﬁnite-state machines), strictly local interaction and communication capabilities (only with particles located in neighboring nodes of the hexagonal grid), and limited motorial capabilities (from a grid node to an empty neighboring node); furthermore, their acti- vation is controlled by an adversarial (but fair) synchronous scheduler. A feature of the Amoebot model is that particles can be in two modes: con- tracted and expanded. When contracted, a particle occupies only one node, while when expanded the particle occupies two neighboring nodes; it is in- deed this ability of a particle to expand and contract that allows it to move on the grid. The Amoebot model has been investigated to understand the computational power of such simple entities; the focus has been on applica- tions such as coating [6, 11], gathering [3], and shape formation [9, 10, 12]. The latter is also the topic of our investigation. The shape formation problem is prototypical for systems of self-organizing entities. This problem, called pattern formation in swarm robotics, requires the entities to move in the spatial universe they inhabit in such a way that, within ﬁnite time, their positions form the geometric shape given in in- put (modulo translation, rotation, scaling, and reﬂection), and no further changes occur. Indeed, this problem has been intensively studied especially in active systems such as autonomous mobile robots (e.g., [1, 5, 14, 15, 25, 29]) and modular robotic systems (e.g., [2, 19, 22]). In the Amoebots model, shape formation has been investigated in [9, 10, 12], taking into account that, due to the ability of particles to expand, it might be possible to form shapes whose size is larger than the number of particles. The pioneering study of [9] on shape formation in the geometric Amoebot model showed how particles can build simple shapes, such as a hexagon or a triangle. Subsequent investigations have recently shown how, starting from a well-structured conﬁguration in which the particles form a (not necessarily complete) triangle, they can form a larger class of shapes [10]. This result has been established under several assumptions: availability of chirality (i.e., a globally consistent circular orientation of the plane shared by all particles), a sequential activation schedule (i.e., at each time unit the scheduler selects only one particle which will interact with its neighbors and possibly move), and, more important, randomization (i.e., particles can ﬂip coins to elect a leader). These results and assumptions immediately and naturally open funda- 3

text: ior

text: of

text: amoeba,

text: programmable

text: matter

text: is

text: viewed

text: as

text: a

text: swarm

text: of

text: decentralized

text: autonomous

text: self-organizing

text: entities,

text: operating

text: on

text: a

text: hexagonal

text: tessellation

text: of

text: the

text: plane.

text: These

text: entities,

text: called

text: particles,

text: are

text: constrained

text: by

text: having

text: sim-

text: ple

text: computational

text: capabilities

text: (they

text: are

text: ﬁnite-state

text: machines),

text: strictly

text: local

text: interaction

text: and

text: communication

text: capabilities

text: (only

text: with

text: particles

text: located

text: in

text: neighboring

text: nodes

text: of

text: the

text: hexagonal

text: grid),

text: and

text: limited

text: motorial

text: capabilities

text: (from

text: a

text: grid

text: node

text: to

text: an

text: empty

text: neighboring

text: node);

text: furthermore,

text: their

text: acti-

text: vation

text: is

text: controlled

text: by

text: an

text: adversarial

text: (but

text: fair)

text: synchronous

text: scheduler.

text: A

text: feature

text: of

text: the

text: Amoebot

text: model

text: is

text: that

text: particles

text: can

text: be

text: in

text: two

text: modes:

text: con-

text: tracted

text: and

text: expanded.

text: When

text: contracted,

text: a

text: particle

text: occupies

text: only

text: one

text: node,

text: while

text: when

text: expanded

text: the

text: particle

text: occupies

text: two

text: neighboring

text: nodes;

text: it

text: is

text: in-

text: deed

text: this

text: ability

text: of

text: a

text: particle

text: to

text: expand

text: and

text: contract

text: that

text: allows

text: it

text: to

text: move

text: on

text: the

text: grid.

text: The

text: Amoebot

text: model

text: has

text: been

text: investigated

text: to

text: understand

text: the

text: computational

text: power

text: of

text: such

text: simple

text: entities;

text: the

text: focus

text: has

text: been

text: on

text: applica-

text: tions

text: such

text: as

text: coating

text: gathering

text: and

text: shape

text: formation

text: The

text: latter

text: is

text: also

text: the

text: topic

text: of

text: our

text: investigation.

text: The

text: shape

text: formation

text: problem

text: is

text: prototypical

text: for

text: systems

text: of

text: self-organizing

text: entities.

text: This

text: problem,

text: called

text: pattern

text: formation

text: in

text: swarm

text: robotics,

text: requires

text: the

text: entities

text: to

text: move

text: in

text: the

text: spatial

text: universe

text: they

text: inhabit

text: in

text: such

text: a

text: way

text: that,

text: within

text: ﬁnite

text: time,

text: their

text: positions

text: form

text: the

text: geometric

text: shape

text: given

text: in

text: in-

text: put

text: (modulo

text: translation,

text: rotation,

text: scaling,

text: and

text: reﬂection),

text: and

text: no

text: further

text: changes

text: occur.

text: Indeed,

text: this

text: problem

text: has

text: been

text: intensively

text: studied

text: especially

text: in

text: active

text: systems

text: such

text: as

text: autonomous

text: mobile

text: robots

text: (e.g.,

text: and

text: modular

text: robotic

text: systems

text: (e.g.,

text: In

text: the

text: Amoebots

text: model,

text: shape

text: formation

text: has

text: been

text: investigated

text: in

text: taking

text: into

text: account

text: that,

text: due

text: to

text: the

text: ability

text: of

text: particles

text: to

text: expand,

text: it

text: might

text: be

text: possible

text: to

text: form

text: shapes

text: whose

text: size

text: is

text: larger

text: than

text: the

text: number

text: of

text: particles.

text: The

text: pioneering

text: study

text: of

text: on

text: shape

text: formation

text: in

text: the

text: geometric

text: Amoebot

text: model

text: showed

text: how

text: particles

text: can

text: build

text: simple

text: shapes,

text: such

text: as

text: a

text: hexagon

text: or

text: a

text: triangle.

text: Subsequent

text: investigations

text: have

text: recently

text: shown

text: how,

text: starting

text: from

text: a

text: well-structured

text: conﬁguration

text: in

text: which

text: the

text: particles

text: form

text: a

text: (not

text: necessarily

text: complete)

text: triangle,

text: they

text: can

text: form

text: a

text: larger

text: class

text: of

text: shapes

text: This

text: result

text: has

text: been

text: established

text: under

text: several

text: assumptions:

text: availability

text: of

text: chirality

text: (i.e.,

text: a

text: globally

text: consistent

text: circular

text: orientation

text: of

text: the

text: plane

text: shared

text: by

text: all

text: particles),

text: a

text: sequential

text: activation

text: schedule

text: (i.e.,

text: at

text: each

text: time

text: unit

text: the

text: scheduler

text: selects

text: only

text: one

text: particle

text: which

text: will

text: interact

text: with

text: its

text: neighbors

text: and

text: possibly

text: move),

text: and,

text: more

text: important,

text: randomization

text: (i.e.,

text: particles

text: can

text: ﬂip

text: coins

text: to

text: elect

text: a

text: leader).

text: These

text: results

text: and

text: assumptions

text: immediately

text: and

text: naturally

text: open

text: funda-


text: themselves (simultaneously). As all of them have to be non-locked corner particles at stage s, it is easy to see that only three conﬁgurations are pos- sible: • At stage s there is only one Eligible particle. Since this is a 0-corner particle, according to the algorithm it will become a Candidate. • At stage s there are only two adjacent 1-corner particles p and p(cid:48). Recall that a particle has to be Stable in order to eliminate itself. Since p is Stable at stage s, it means that there is a stage s(cid:48) < s during which p has already sent a message to p(cid:48) saying that it was a 1-corner particle (otherwise, some neighbor of p would have eliminated itself in the meantime, implying that p would not be Stable). Since p(cid:48) is active at stage s, it must receive or have already received the message sent at time s(cid:48) by p. So, p(cid:48) knows that p is a 1-corner, and hence it becomes a Candidate (and vice versa). • At stage s there are only three pairwise adjacent 2-corner particles. Reasoning as in the previous case, we see that, since all three particles are Stable at stage s, they know that they are all 2-corner particles, and therefore they become Candidates. In all cases, at least one particle becomes a Candidate, contradicting our assumption. Finally, the upper bound of O(n) rounds easily follows from the fact that, in a constant number of rounds, at least one corner particle becomes non-Eligible or a Candidate. This happens at most n − 1 times, until only Candidates are left. 3.2 Spanning Forest Construction Phase Algorithm. The spanning forest construction phase starts when 1, 2, or 3 pairwise adjacent candidate leaders have been identiﬁed, and no other particle is Eligible. In this phase, each candidate leader becomes the root of a tree embedded in G. Eventually, the set of these trees will be a spanning forest of the subgraph of G induced by the system P . Each particle has a ﬂag called Tree, initially not set, whose purpose is to indicate that the particle has been included in a tree. Moreover, each particle also has a variable called Parent, which contains the local port number corresponding to its parent, provided that the particle is part of a tree (the initial value of this variable is −1). 22 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: themselves

text: (simultaneously).

text: As

text: all

text: of

text: them

text: have

text: to

text: be

text: non-locked

text: corner

text: particles

text: at

text: stage

text: s,

text: it

text: is

text: easy

text: to

text: see

text: that

text: only

text: three

text: conﬁgurations

text: are

text: pos-

text: sible:

label: list

text: At

text: stage

text: s

text: there

text: is

text: only

text: one

text: Eligible

text: particle.

text: Since

text: this

text: is

text: a

text: particle,

text: according

text: to

text: the

text: algorithm

text: it

text: will

text: become

text: a

text: Candidate.

text: At

text: stage

text: s

text: there

text: are

text: only

text: two

text: adjacent

text: particles

text: p

text: and

text: Recall

text: that

text: a

text: particle

text: has

text: to

text: be

text: Stable

text: in

text: order

text: to

text: eliminate

text: itself.

text: Since

text: p

text: is

text: Stable

text: at

text: stage

text: s,

text: it

text: means

text: that

text: there

text: is

text: a

text: stage

text: s

text: during

text: which

text: p

text: has

text: already

text: sent

text: a

text: message

text: to

text: saying

text: that

text: it

text: was

text: a

text: particle

text: (otherwise,

text: some

text: neighbor

text: of

text: p

text: would

text: have

text: eliminated

text: itself

text: in

text: the

text: meantime,

text: implying

text: that

text: p

text: would

text: not

text: be

text: Stable).

text: Since

text: is

text: active

text: at

text: stage

text: s,

text: it

text: must

text: receive

text: or

text: have

text: already

text: received

text: the

text: message

text: sent

text: at

text: time

text: by

text: p.

text: So,

text: knows

text: that

text: p

text: is

text: a

text: and

text: hence

text: it

text: becomes

text: a

text: Candidate

text: (and

text: vice

text: versa).

text: At

text: stage

text: s

text: there

text: are

text: only

text: three

text: pairwise

text: adjacent

text: particles.

text: Reasoning

text: as

text: in

text: the

text: previous

text: case,

text: we

text: see

text: that,

text: since

text: all

text: three

text: particles

text: are

text: Stable

text: at

text: stage

text: s,

text: they

text: know

text: that

text: they

text: are

text: all

text: particles,

text: and

text: therefore

text: they

text: become

text: Candidates.

text: In

text: all

text: cases,

text: at

text: least

text: one

text: particle

text: becomes

text: a

text: Candidate,

text: contradicting

text: our

text: assumption.

text: Finally,

text: the

text: upper

text: bound

text: of

text: O(n)

text: rounds

text: easily

text: follows

text: from

text: the

text: fact

text: that,

text: in

text: a

text: constant

text: number

text: of

text: rounds,

text: at

text: least

text: one

text: corner

text: particle

text: becomes

text: non-Eligible

text: or

text: a

text: Candidate.

text: This

text: happens

text: at

text: most

text: n

text: times,

text: until

text: only

text: Candidates

text: are

text: left.

text: Spanning

text: Forest

text: Construction

text: Phase

text: Algorithm.

text: The

text: spanning

text: forest

text: construction

text: phase

text: starts

text: when

text: or

text: pairwise

text: adjacent

text: candidate

text: leaders

text: have

text: been

text: identiﬁed,

text: and

text: no

text: other

text: particle

text: is

text: Eligible.

text: In

text: this

text: phase,

text: each

text: candidate

text: leader

text: becomes

text: the

text: root

text: of

text: a

text: tree

text: embedded

text: in

text: G.

text: Eventually,

text: the

text: set

text: of

text: these

text: trees

text: will

text: be

text: a

text: spanning

text: forest

text: of

text: the

text: subgraph

text: of

text: G

text: induced

text: by

text: the

text: system

text: P

text: Each

text: particle

text: has

text: a

text: ﬂag

text: called

text: Tree,

text: initially

text: not

text: set,

text: whose

text: purpose

text: is

text: to

text: indicate

text: that

text: the

text: particle

text: has

text: been

text: included

text: in

text: a

text: tree.

text: Moreover,

text: each

text: particle

text: also

text: has

text: a

text: variable

text: called

text: Parent,

text: which

text: contains

text: the

text: local

text: port

text: number

text: corresponding

text: to

text: its

text: parent,

text: provided

text: that

text: the

text: particle

text: is

text: part

text: of

text: a

text: tree

text: (the

text: initial

text: value

text: of

text: this

text: variable

text: is

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: As in the previous phase, all particles send information to their neighbors containing part of their internal states. This information is recorded by the receiving particles: so, each particle has an Is-in-Tree ﬂag and an Is-my- Child ﬂag corresponding to each neighbor. All these ﬂag are initially not set. Finally, there is a Tree-Done ﬂag (initially not set) corresponding to each neighbor, which is used in the last part of the phase. The following rules apply to all particles during the spanning forest con- struction phase: • If a particle’s Candidate ﬂag is set and its Tree ﬂag is not set, it sets its own Tree ﬂag and leaves its own Parent ﬂag to −1 (implying that it is the root of a tree). • If a particle’s Tree ﬂag is set, it sends a Parent message to the port corresponding to its own Parent variable (assuming it is not −1), and it sends a Tree message to all other neighbors. • If a particle receives a Tree message from a neighbor, it sets the Is-in- Tree ﬂag relative to its port. Similarly, if it receives a Parent message from a neighbor, it sets both the Is-in-Tree and the Is-my-Child ﬂag relative to its port. • If a particle’s Candidate ﬂag is not set, its Tree ﬂag is not set, and the Is-in-Tree ﬂags relative to some of its neighbors are set, then it sets its own Tree ﬂag. Let k be the smallest port number corresponding to a neighbor whose relative Is-in-Tree ﬂag is set. Then, the particle sets its own Parent ﬂag to k (implying that that neighbor is now its parent). • If a particle p’s Tree ﬂag is set, the Is-in-Tree ﬂags corresponding to all its neighbors are set, and the Tree-Done ﬂags relative to all it children are set (recall that its children are the neighbors whose relative Is-my- Child ﬂag is set), then: – If p has a parent (i.e., its Parent variable is not −1), it sends a Tree-Done message to its parent. – If p has no parent (i.e., it is a candidate leader), it sends a Tree- Done message to its Candidate neighbors. • If a particle receives a Tree-Done message from one of its children, it sets the corresponding Tree-Done ﬂag. 23

text: As

text: in

text: the

text: previous

text: phase,

text: all

text: particles

text: send

text: information

text: to

text: their

text: neighbors

text: containing

text: part

text: of

text: their

text: internal

text: states.

text: This

text: information

text: is

text: recorded

text: by

text: the

text: receiving

text: particles:

text: so,

text: each

text: particle

text: has

text: an

text: Is-in-Tree

text: ﬂag

text: and

text: an

text: Is-my-

text: Child

text: ﬂag

text: corresponding

text: to

text: each

text: neighbor.

text: All

text: these

text: ﬂag

text: are

text: initially

text: not

text: set.

text: Finally,

text: there

text: is

text: a

text: Tree-Done

text: ﬂag

text: (initially

text: not

text: set)

text: corresponding

text: to

text: each

text: neighbor,

text: which

text: is

text: used

text: in

text: the

text: last

text: part

text: of

text: the

text: phase.

text: The

text: following

text: rules

text: apply

text: to

text: all

text: particles

text: during

text: the

text: spanning

text: forest

text: con-

text: struction

text: phase:

text: If

text: a

text: particle’s

text: Candidate

text: ﬂag

text: is

text: set

text: and

text: its

text: Tree

text: ﬂag

text: is

text: not

text: set,

text: it

text: sets

text: its

text: own

text: Tree

text: ﬂag

text: and

text: leaves

text: its

text: own

text: Parent

text: ﬂag

text: to

text: −1

text: (implying

text: that

text: it

text: is

text: the

text: root

text: of

text: a

text: tree).

text: If

text: a

text: particle’s

text: Tree

text: ﬂag

text: is

text: set,

text: it

text: sends

text: a

text: Parent

text: message

text: to

text: the

text: port

text: corresponding

text: to

text: its

text: own

text: Parent

text: variable

text: (assuming

text: it

text: is

text: not

text: and

text: it

text: sends

text: a

text: Tree

text: message

text: to

text: all

text: other

text: neighbors.

text: If

text: a

text: particle

text: receives

text: a

text: Tree

text: message

text: from

text: a

text: neighbor,

text: it

text: sets

text: the

text: Is-in-

text: Tree

text: ﬂag

text: relative

text: to

text: its

text: port.

text: Similarly,

text: if

text: it

text: receives

text: a

text: Parent

text: message

text: from

text: a

text: neighbor,

text: it

text: sets

text: both

text: the

text: Is-in-Tree

text: and

text: the

text: Is-my-Child

text: ﬂag

text: relative

text: to

text: its

text: port.

text: If

text: a

text: particle’s

text: Candidate

text: ﬂag

text: is

text: not

text: set,

text: its

text: Tree

text: ﬂag

text: is

text: not

text: set,

text: and

text: the

text: Is-in-Tree

text: ﬂags

text: relative

text: to

text: some

text: of

text: its

text: neighbors

text: are

text: set,

text: then

text: it

text: sets

text: its

text: own

text: Tree

text: ﬂag.

text: Let

text: k

text: be

text: the

text: smallest

text: port

text: number

text: corresponding

text: to

text: a

text: neighbor

text: whose

text: relative

text: Is-in-Tree

text: ﬂag

text: is

text: set.

text: Then,

text: the

text: particle

text: sets

text: its

text: own

text: Parent

text: ﬂag

text: to

text: k

text: (implying

text: that

text: that

text: neighbor

text: is

text: now

text: its

text: parent).

text: If

text: a

text: particle

text: p’s

text: Tree

text: ﬂag

text: is

text: set,

text: the

text: Is-in-Tree

text: ﬂags

text: corresponding

text: to

text: all

text: its

text: neighbors

text: are

text: set,

text: and

text: the

text: Tree-Done

text: ﬂags

text: relative

text: to

text: all

text: it

text: children

text: are

text: set

text: (recall

text: that

text: its

text: children

text: are

text: the

text: neighbors

text: whose

text: relative

text: Is-my-

text: Child

text: ﬂag

text: is

text: set),

text: then:

text: If

text: p

text: has

text: a

text: parent

text: (i.e.,

text: its

text: Parent

text: variable

text: is

text: not

text: it

text: sends

text: a

text: Tree-Done

text: message

text: to

text: its

text: parent.

text: If

text: p

text: has

text: no

text: parent

text: (i.e.,

text: it

text: is

text: a

text: candidate

text: leader),

text: it

text: sends

text: a

text: Tree-

text: Done

text: message

text: to

text: its

text: Candidate

text: neighbors.

text: If

text: a

text: particle

text: receives

text: a

text: Tree-Done

text: message

text: from

text: one

text: of

text: its

text: children,

text: it

text: sets

text: the

text: corresponding

text: Tree-Done

text: ﬂag.


text: Correctness. Theorem 4. Let P be the system resulting from Theorem 3. If all particles of P execute the spanning forest construction phase of the algorithm, then there is a stage, reached after O(n) rounds, where every particle has the Tree ﬂag set, each non-Candidate particle has a unique parent, and each particle has received a Tree-Done message from all its children. No particle moves in this phase. Proof. It is easy to prove by induction that, at every stage, the Tree parti- cles form a forest with a tree rooted in each Candidate particle, and that the Parent variables of all Tree particles are consistent. Indeed, when any (posi- tive) number of neighbors of a non-Tree particle p become Tree particles and start sending Tree messages to p, p chooses one of them as its parent as soon as it is activated, and sets its ﬂags accordingly. It then communicates this change to its neighbors, which update their Is-in-Tree and the Is-my-Child ﬂags consistently. Since P forms a connected shape (because it results from Theorem 3), eventually all particles become part of some tree, and a spanning forest is constructed. So, eventually, some leaves of the forest observe that all their neighbors are Tree particles (because all their relative Is-in-Tree ﬂags are set) and none of them is their child (because none of their relative Is-my-Child ﬂags is set). These leaves send Tree-Done messages to their parents. As more leaves send Tree-Done messages to their parents, some internal particles start observing that all their children are sending Tree-Done mes- sages, and all other neighbors are Tree particles. These internal particles therefore send Tree-Done messages to their parents, as well. Eventually, the Candidate particles will receive Tree-Done messages from all their children. At this stage, every particle has the Tree ﬂag set, each non-Candidate parti- cle has a unique parent, and each particle has received a Tree-Done message from all its children. To show that the phase ends in O(n) rounds, it suﬃces to note that in a constant number of rounds either a new particle sets its Tree ﬂag or forwards the Tree-Done message to its parent (or its Candidate neighbors if it has no parent). 3.3 Handedness Agreement Phase When a candidate leader has received Tree messages from all its neigh- bors and Tree-Done messages from all its children, it transitions to the 24 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Correctness.

text: Theorem

text: Let

text: P

text: be

text: the

text: system

text: resulting

text: from

text: Theorem

text: If

text: all

text: particles

text: of

text: P

text: execute

text: the

text: spanning

text: forest

text: construction

text: phase

text: of

text: the

text: algorithm,

text: then

text: there

text: is

text: a

text: stage,

text: reached

text: after

text: O(n)

text: rounds,

text: where

text: every

text: particle

text: has

text: the

text: Tree

text: ﬂag

text: set,

text: each

text: non-Candidate

text: particle

text: has

text: a

text: unique

text: parent,

text: and

text: each

text: particle

text: has

text: received

text: a

text: Tree-Done

text: message

text: from

text: all

text: its

text: children.

text: No

text: particle

text: moves

text: in

text: this

text: phase.

text: Proof.

text: It

text: is

text: easy

text: to

text: prove

text: by

text: induction

text: that,

text: at

text: every

text: stage,

text: the

text: Tree

text: parti-

text: cles

text: form

text: a

text: forest

text: with

text: a

text: tree

text: rooted

text: in

text: each

text: Candidate

text: particle,

text: and

text: that

text: the

text: Parent

text: variables

text: of

text: all

text: Tree

text: particles

text: are

text: consistent.

text: Indeed,

text: when

text: any

text: (posi-

text: tive)

text: number

text: of

text: neighbors

text: of

text: a

text: non-Tree

text: particle

text: p

text: become

text: Tree

text: particles

text: and

text: start

text: sending

text: Tree

text: messages

text: to

text: p,

text: p

text: chooses

text: one

text: of

text: them

text: as

text: its

text: parent

text: as

text: soon

text: as

text: it

text: is

text: activated,

text: and

text: sets

text: its

text: ﬂags

text: accordingly.

text: It

text: then

text: communicates

text: this

text: change

text: to

text: its

text: neighbors,

text: which

text: update

text: their

text: Is-in-Tree

text: and

text: the

text: Is-my-Child

text: ﬂags

text: consistently.

text: Since

text: P

text: forms

text: a

text: connected

text: shape

text: (because

text: it

text: results

text: from

text: Theorem

text: eventually

text: all

text: particles

text: become

text: part

text: of

text: some

text: tree,

text: and

text: a

text: spanning

text: forest

text: is

text: constructed.

text: So,

text: eventually,

text: some

text: leaves

text: of

text: the

text: forest

text: observe

text: that

text: all

text: their

text: neighbors

text: are

text: Tree

text: particles

text: (because

text: all

text: their

text: relative

text: Is-in-Tree

text: ﬂags

text: are

text: set)

text: and

text: of

text: them

text: is

text: their

text: child

text: (because

text: of

text: their

text: relative

text: Is-my-Child

text: ﬂags

text: is

text: set).

text: These

text: leaves

text: send

text: Tree-Done

text: messages

text: to

text: their

text: parents.

text: As

text: more

text: leaves

text: send

text: Tree-Done

text: messages

text: to

text: their

text: parents,

text: some

text: internal

text: particles

text: start

text: observing

text: that

text: all

text: their

text: children

text: are

text: sending

text: Tree-Done

text: mes-

text: sages,

text: and

text: all

text: other

text: neighbors

text: are

text: Tree

text: particles.

text: These

text: internal

text: particles

text: therefore

text: send

text: Tree-Done

text: messages

text: to

text: their

text: parents,

text: as

text: well.

text: Eventually,

text: the

text: Candidate

text: particles

text: will

text: receive

text: Tree-Done

text: messages

text: from

text: all

text: their

text: children.

text: At

text: this

text: stage,

text: every

text: particle

text: has

text: the

text: Tree

text: ﬂag

text: set,

text: each

text: non-Candidate

text: parti-

text: cle

text: has

text: a

text: unique

text: parent,

text: and

text: each

text: particle

text: has

text: received

text: a

text: Tree-Done

text: message

text: from

text: all

text: its

text: children.

text: To

text: show

text: that

text: the

text: phase

text: ends

text: in

text: O(n)

text: rounds,

text: it

text: suﬃces

text: to

text: note

text: that

text: in

text: a

text: constant

text: number

text: of

text: rounds

text: either

text: a

text: new

text: particle

text: sets

text: its

text: Tree

text: ﬂag

text: or

text: forwards

text: the

text: Tree-Done

text: message

text: to

text: its

text: parent

text: (or

text: its

text: Candidate

text: neighbors

text: if

text: it

text: has

text: no

text: parent).

text: Handedness

text: Agreement

text: Phase

text: When

text: a

text: candidate

text: leader

text: has

text: received

text: Tree

text: messages

text: from

text: all

text: its

text: neigh-

text: bors

text: and

text: Tree-Done

text: messages

text: from

text: all

text: its

text: children,

text: it

text: transitions

text: to

text: the

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: handedness agreement phase. Recall that each particle may label ports in clockwise or counterclockwise order: this is called the particle’s handedness. By the end of this phase, all particles will agree on a common handedness. The agreement process starts at the candidate leaders and proceeds through the spanning forest constructed in the previous phase, from parents to chil- dren. Agreement among candidate leaders. In the ﬁrst stages of this phase, the candidate leaders agree on a common handedness. This may result in the “elimination” of some of them. If there is a unique candidate leader, this part of the algorithm is trivial. So, let us assume that there are two or three candidate leaders. Suppose that there are two candidate leaders p and p(cid:48). Then, they have exactly two neighboring vertices u and v in common. By now, the candidate leaders know if u and v are occupied or not. There are three cases. • Exactly one between u and v is occupied. Without loss of generality, u is occupied by a particle p , and v is unoccupied. Then, both p and p(cid:48) u send a You-Choose message to p . When p has received You-Choose u u messages from both, it arbitrarily picks one between p and p(cid:48), say p. Then p sends a Chosen message to p and a Not-Chosen message to u p(cid:48). As a consequence, p(cid:48) ceases to be a candidate leader (by clearing its own Candidate and Eligible ﬂags), and p becomes the parent of p(cid:48) (i.e., the Parent variable of p(cid:48) and the Is-my-Child variables of p are appropriately updated). • u is occupied by a particle p and v is occupied by a particle p . u v Let the edge {p, p(cid:48)} be labeled i by p, and observe that i − (cid:96)(p, u) ≡ −i + (cid:96)(p, v) ≡ ±1 (mod 6). Without loss of generality, i − (cid:96)(p, u) ≡ 1 (mod 6). Then, p sends a You-Choose message to p and a You-do- u not-Choose message to p . p(cid:48) does the same. If one between p or v u p receives both You-Choose messages, it arbitrarily eliminates one v between p and p(cid:48), as explained above. Otherwise, both p and p u v receive a You-Choose message and a You-do-not-Choose message. This means that p and p(cid:48) have the same handedness. So, p and p send u v Same-Handedness messages to both p and p(cid:48), who wait until they receive both messages. • Both u and v are unoccupied. As above, if the edge {p, p(cid:48)} is labeled i by p, then i − (cid:96)(p, u) ≡ −i + (cid:96)(p, v) ≡ ±1 (mod 6). Without loss of generality, assume that i − (cid:96)(p, u) ≡ 1 (mod 6). Then, p attempts to expand toward u. Meanwhile, p(cid:48) does the same. 25

text: handedness

text: agreement

text: phase.

text: Recall

text: that

text: each

text: particle

text: may

text: label

text: ports

text: in

text: clockwise

text: or

text: counterclockwise

text: order:

text: this

text: is

text: called

text: the

text: particle’s

text: handedness.

text: By

text: the

text: end

text: of

text: this

text: phase,

text: all

text: particles

text: will

text: agree

text: on

text: a

text: common

text: handedness.

text: The

text: agreement

text: process

text: starts

text: at

text: the

text: candidate

text: leaders

text: and

text: proceeds

text: through

text: the

text: spanning

text: forest

text: constructed

text: in

text: the

text: previous

text: phase,

text: from

text: parents

text: to

text: chil-

text: dren.

text: Agreement

text: among

text: candidate

text: leaders.

text: In

text: the

text: ﬁrst

text: stages

text: of

text: this

text: phase,

text: the

text: candidate

text: leaders

text: agree

text: on

text: a

text: common

text: handedness.

text: This

text: may

text: result

text: in

text: the

text: “elimination”

text: of

text: some

text: of

text: them.

text: If

text: there

text: is

text: a

text: unique

text: candidate

text: leader,

text: this

text: part

text: of

text: the

text: algorithm

text: is

text: trivial.

text: So,

text: let

text: us

text: assume

text: that

text: there

text: are

text: two

text: or

text: three

text: candidate

text: leaders.

text: Suppose

text: that

text: there

text: are

text: two

text: candidate

text: leaders

text: p

text: and

text: Then,

text: they

text: have

text: exactly

text: two

text: neighboring

text: vertices

text: u

text: and

text: v

text: in

text: common.

text: By

text: now,

text: the

text: candidate

text: leaders

text: know

text: if

text: u

text: and

text: v

text: are

text: occupied

text: or

text: not.

text: There

text: are

text: three

text: cases.

text: Exactly

text: one

text: between

text: u

text: and

text: v

text: is

text: occupied.

text: Without

text: loss

text: of

text: generality,

text: u

text: is

text: occupied

text: by

text: a

text: particle

text: p

text: and

text: v

text: is

text: unoccupied.

text: Then,

text: both

text: p

text: and

text: u

text: send

text: a

text: You-Choose

text: message

text: to

text: p

text: When

text: p

text: has

text: received

text: You-Choose

text: u

text: u

text: messages

text: from

text: both,

text: it

text: arbitrarily

text: picks

text: one

text: between

text: p

text: and

text: say

text: p.

text: Then

text: p

text: sends

text: a

text: Chosen

text: message

text: to

text: p

text: and

text: a

text: Not-Chosen

text: message

text: to

text: u

text: As

text: a

text: consequence,

text: ceases

text: to

text: be

text: a

text: candidate

text: leader

text: (by

text: clearing

text: its

text: own

text: Candidate

text: and

text: Eligible

text: ﬂags),

text: and

text: p

text: becomes

text: the

text: parent

text: of

text: (i.e.,

text: the

text: Parent

text: variable

text: of

text: and

text: the

text: Is-my-Child

text: variables

text: of

text: p

text: are

text: appropriately

text: updated).

text: u

text: is

text: occupied

text: by

text: a

text: particle

text: p

text: and

text: v

text: is

text: occupied

text: by

text: a

text: particle

text: p

text: u

text: v

text: Let

text: the

text: edge

text: {p,

text: be

text: labeled

text: i

text: by

text: p,

text: and

text: observe

text: that

text: i

text: u)

text: −i

text: v)

text: ±1

text: (mod

text: Without

text: loss

text: of

text: generality,

text: i

text: u)

text: (mod

text: Then,

text: p

text: sends

text: a

text: You-Choose

text: message

text: to

text: p

text: and

text: a

text: You-do-

text: u

text: not-Choose

text: message

text: to

text: p

text: does

text: the

text: same.

text: If

text: one

text: between

text: p

text: or

text: v

text: u

text: p

text: receives

text: both

text: You-Choose

text: messages,

text: it

text: arbitrarily

text: eliminates

text: one

text: v

text: between

text: p

text: and

text: as

text: explained

text: above.

text: Otherwise,

text: both

text: p

text: and

text: p

text: u

text: v

text: receive

text: a

text: You-Choose

text: message

text: and

text: a

text: You-do-not-Choose

text: message.

text: This

text: means

text: that

text: p

text: and

text: have

text: the

text: same

text: handedness.

text: So,

text: p

text: and

text: p

text: send

text: u

text: v

text: Same-Handedness

text: messages

text: to

text: both

text: p

text: and

text: who

text: wait

text: until

text: they

text: receive

text: both

text: messages.

text: Both

text: u

text: and

text: v

text: are

text: unoccupied.

text: As

text: above,

text: if

text: the

text: edge

text: {p,

text: is

text: labeled

text: i

text: by

text: p,

text: then

text: i

text: u)

text: −i

text: v)

text: ±1

text: (mod

text: Without

text: loss

text: of

text: generality,

text: assume

text: that

text: i

text: u)

text: (mod

text: Then,

text: p

text: attempts

text: to

text: expand

text: toward

text: u.

text: Meanwhile,

text: does

text: the

text: same.


text: mental research questions, including: Are other shapes formable? What can be done deterministically? Is chirality necessary? as well as some less crucial but nevertheless interesting questions, such as: What happens if the scheduler is not sequential? What if the initial conﬁguration is not well structured? In this paper, motivated and stimulated by these questions, we continue the investigation on shape formation in the geometric Amoebot model and provide some deﬁnitive answers. 1.2 Main Contributions We establish several results that, among other things, provide a con- structive characterization of which shapes S can be formed deterministi- F cally starting from an unknown simply connected initial conﬁguration S of 0 n particles. As in [10], we assume that the size of the description of S is constant F with respect to the size of the system, so that it can be encoded by each particle as part of its internal memory. Such a description is available to all the particles at the beginning of the execution, and we call it their “input”. The particles will form a ﬁnal conﬁguration that is an appropriate scaling, translation, rotation, and perhaps reﬂection of the input shape S . Since F all particles of S must be used to construct S , the scale λ of the ﬁnal 0 F conﬁguration depends on n: we stress that λ is unknown to particles, and they must determine it autonomously. Given two shapes S and S , we say that the pair (S , S ) is feasible if 0 F 0 F there exists a deterministic algorithm that, in every execution and regardless of the activation schedule, allows the particles to form S starting from S F 0 and no longer move. On the contrary, a pair (S , S ) of shapes is unfeasible when the symme- 0 F try of the initial conﬁguration S prevents the formation of the ﬁnal shape 0 S . In Section , we formalize the notion of unbreakable symmetry of shapes F embedded in triangular grids, and in Theorem 1 we show that starting from an unbreakable k-symmetric conﬁguration only unbreakable k-symmetric shapes can be formed. Interestingly, for all the feasible pairs, we provide a universal shape for- mation algorithm in Section . This algorithm does not need any information on S , except that it is simply connected. 0 These results concern the deterministic formation of shapes. As a mat- ter of fact, our algorithm uses a deterministic leader election algorithm as a subroutine (Sections –). If the initial shape S is unbreakably k-symmetric, 0 such an algorithm may elect as many as k neighboring leader particles, where 4

text: mental

text: research

text: questions,

text: including:

text: Are

text: other

text: shapes

text: formable?

text: What

text: can

text: be

text: done

text: deterministically?

text: Is

text: chirality

text: necessary?

text: as

text: well

text: as

text: some

text: less

text: crucial

text: but

text: nevertheless

text: interesting

text: questions,

text: such

text: as:

text: What

text: happens

text: if

text: the

text: scheduler

text: is

text: not

text: sequential?

text: What

text: if

text: the

text: initial

text: conﬁguration

text: is

text: not

text: well

text: structured?

text: In

text: this

text: paper,

text: motivated

text: and

text: stimulated

text: by

text: these

text: questions,

text: we

text: continue

text: the

text: investigation

text: on

text: shape

text: formation

text: in

text: the

text: geometric

text: Amoebot

text: model

text: and

text: provide

text: some

text: deﬁnitive

text: answers.

label: section

text: Main

text: Contributions

text: We

text: establish

text: several

text: results

text: that,

text: among

text: other

text: things,

text: provide

text: a

text: con-

text: structive

text: characterization

text: of

text: which

text: shapes

text: S

text: can

text: be

text: formed

text: deterministi-

text: F

text: cally

text: starting

text: from

text: an

text: unknown

text: simply

text: connected

text: initial

text: conﬁguration

text: S

text: of

text: n

text: particles.

text: As

text: in

text: we

text: assume

text: that

text: the

text: size

text: of

text: the

text: description

text: of

text: S

text: is

text: constant

text: F

text: with

text: respect

text: to

text: the

text: size

text: of

text: the

text: system,

text: so

text: that

text: it

text: can

text: be

text: encoded

text: by

text: each

text: particle

text: as

text: part

text: of

text: its

text: internal

text: memory.

text: Such

text: a

text: description

text: is

text: available

text: to

text: all

text: the

text: particles

text: at

text: the

text: beginning

text: of

text: the

text: execution,

text: and

text: we

text: call

text: it

text: their

text: “input”.

text: The

text: particles

text: will

text: form

text: a

text: ﬁnal

text: conﬁguration

text: that

text: is

text: an

text: appropriate

text: scaling,

text: translation,

text: rotation,

text: and

text: perhaps

text: reﬂection

text: of

text: the

text: input

text: shape

text: S

text: Since

text: F

text: all

text: particles

text: of

text: S

text: must

text: be

text: used

text: to

text: construct

text: S

text: the

text: scale

text: λ

text: of

text: the

text: ﬁnal

text: F

text: conﬁguration

text: depends

text: on

text: n:

text: we

text: stress

text: that

text: λ

text: is

text: unknown

text: to

text: particles,

text: and

text: they

text: must

text: determine

text: it

text: autonomously.

text: Given

text: two

text: shapes

text: S

text: and

text: S

text: we

text: say

text: that

text: the

text: pair

text: (S

text: S

text: is

text: feasible

text: if

text: F

text: F

text: there

text: exists

text: a

text: deterministic

text: algorithm

text: that,

text: in

text: every

text: execution

text: and

text: regardless

text: of

text: the

text: activation

text: schedule,

text: allows

text: the

text: particles

text: to

text: form

text: S

text: starting

text: from

text: S

text: F

text: and

text: no

text: longer

text: move.

text: On

text: the

text: contrary,

text: a

text: pair

text: (S

text: S

text: of

text: shapes

text: is

text: unfeasible

text: when

text: the

text: symme-

text: F

text: try

text: of

text: the

text: initial

text: conﬁguration

text: S

text: prevents

text: the

text: formation

text: of

text: the

text: ﬁnal

text: shape

text: S

text: In

text: Section

text: we

text: formalize

text: the

text: notion

text: of

text: unbreakable

text: symmetry

text: of

text: shapes

text: F

text: embedded

text: in

text: triangular

text: grids,

text: and

text: in

text: Theorem

text: we

text: show

text: that

text: starting

text: from

text: an

text: unbreakable

text: k-symmetric

text: conﬁguration

text: only

text: unbreakable

text: k-symmetric

text: shapes

text: can

text: be

text: formed.

text: Interestingly,

text: for

text: all

text: the

text: feasible

text: pairs,

text: we

text: provide

text: a

text: universal

text: shape

text: for-

text: mation

text: algorithm

text: in

text: Section

text: This

text: algorithm

text: does

text: not

text: need

text: any

text: information

text: on

text: S

text: except

text: that

text: it

text: is

text: simply

text: connected.

text: These

text: results

text: concern

text: the

text: deterministic

text: formation

text: of

text: shapes.

text: As

text: a

text: mat-

text: ter

text: of

text: fact,

text: our

text: algorithm

text: uses

text: a

text: deterministic

text: leader

text: election

text: algorithm

text: as

text: a

text: subroutine

text: (Sections

text: If

text: the

text: initial

text: shape

text: S

text: is

text: unbreakably

text: k-symmetric,

text: such

text: an

text: algorithm

text: may

text: elect

text: as

text: many

text: as

text: k

text: neighboring

text: leader

text: particles,

text: where


text: system, n (cf. Section ). Also, we may assume S to be a minimal shape: if F it is not, the particles replace its representation with that of a minimal shape equivalent to S , which has a smaller size and is readily computable. Finally, F since the handedness agreement phase has been completed, all the particles can be assumed to have the same handedness (see Theorem 5). Without loss of generality, we assume that their notion of clockwise direction coincides with the “correct” one, i.e., the one deﬁned by the cross product of vectors R in 2. The goal of the role assignment phase is twofold: • The particles determine the scale of the shape S(cid:48) , equivalent to S , F F that they are going to form. Indeed, if n is large enough, there is a scaled-up copy of S that can be formed by exactly n particles, keeping F in mind that, in the ﬁnal conﬁguration, particles can be contracted or expanded. • Each particle is assigned a constant-size identiﬁer, describing which element of S (i.e., a vertex, the interior of an edge, or the interior F of a triangle) the particle is going to form in the shape composition phase. Recall that we are assuming S to be composed of a constant F (i.e., independent of n) number of triangles and edges, in accordance to the deﬁnition of universal shape formation (see Section ). The size of the identiﬁer is proportional to the size of S , and can therefore be F stored in a single particle’s internal memory. Subdividing the ﬁnal shape into elements. Recall that a shape is the union of ﬁnitely many edges and faces of G . Of course, all edges of G D D have length 1, and all faces of G are equilateral triangles of side length 1. D Let the ﬁnal shape S be of the form S = e ∪ · · · ∪ e ∪ t ∪ · · · ∪ t (cid:48), where F F 1 j 1 j the e ’s are edges of G and the t ’s are (triangular) faces of G . i D i D Let S(cid:48) be a shape equivalent to S . By Lemma 1, the scale of S(cid:48) is a F F F positive integer λ (recall that S is minimal). That is, there is a similarity F R R transformation σ : 2 → 2 such that σ(e ) is a segment of length λ (i.e., it i is the union of λ consecutive segments of G ) contained in S(cid:48) and σ(t ) is D F i an equilateral triangle of side length λ contained in S(cid:48) . F Let B be the set of vertices of G that are contained in S(cid:48) . We partition D F B into three families of elements as follows: • If v is a vertex of G contained in S , then σ(v) constitutes a super- D F vertex of S(cid:48) . F • For every e , the vertices of G that are contained in σ(e ) and are i D i not super-vertices of S(cid:48) constitute a super-edge of S(cid:48) . Similarly, for F F 44

text: system,

text: n

text: (cf.

text: Section

text: Also,

text: we

text: may

text: assume

text: S

text: to

text: be

text: a

text: minimal

text: shape:

text: if

text: F

text: it

text: is

text: not,

text: the

text: particles

text: replace

text: its

text: representation

text: with

text: that

text: of

text: a

text: minimal

text: shape

text: equivalent

text: to

text: S

text: which

text: has

text: a

text: smaller

text: size

text: and

text: is

text: readily

text: computable.

text: Finally,

text: F

text: since

text: the

text: handedness

text: agreement

text: phase

text: has

text: been

text: completed,

text: all

text: the

text: particles

text: can

text: be

text: assumed

text: to

text: have

text: the

text: same

text: handedness

text: (see

text: Theorem

text: Without

text: loss

text: of

text: generality,

text: we

text: assume

text: that

text: their

text: notion

text: of

text: clockwise

text: direction

text: coincides

text: with

text: the

text: “correct”

text: one,

text: i.e.,

text: the

text: one

text: deﬁned

text: by

text: the

text: cross

text: product

text: of

text: vectors

text: R

text: in

text: The

text: goal

text: of

text: the

text: role

text: assignment

text: phase

text: is

text: twofold:

text: The

text: particles

text: determine

text: the

text: scale

text: of

text: the

text: shape

text: equivalent

text: to

text: S

text: F

text: F

text: that

text: they

text: are

text: going

text: to

text: form.

text: Indeed,

text: if

text: n

text: is

text: large

text: enough,

text: there

text: is

text: a

text: scaled-up

text: copy

text: of

text: S

text: that

text: can

text: be

text: formed

text: by

text: exactly

text: n

text: particles,

text: keeping

text: F

text: in

text: mind

text: that,

text: in

text: the

text: ﬁnal

text: conﬁguration,

text: particles

text: can

text: be

text: contracted

text: or

text: expanded.

text: Each

text: particle

text: is

text: assigned

text: a

text: constant-size

text: identiﬁer,

text: describing

text: which

text: element

text: of

text: S

text: (i.e.,

text: a

text: vertex,

text: the

text: interior

text: of

text: an

text: edge,

text: or

text: the

text: interior

text: F

text: of

text: a

text: triangle)

text: the

text: particle

text: is

text: going

text: to

text: form

text: in

text: the

text: shape

text: composition

text: phase.

text: Recall

text: that

text: we

text: are

text: assuming

text: S

text: to

text: be

text: composed

text: of

text: a

text: constant

text: F

text: (i.e.,

text: independent

text: of

text: n)

text: number

text: of

text: triangles

text: and

text: edges,

text: in

text: accordance

text: to

text: the

text: deﬁnition

text: of

text: universal

text: shape

text: formation

text: (see

text: Section

text: The

text: size

text: of

text: the

text: identiﬁer

text: is

text: proportional

text: to

text: the

text: size

text: of

text: S

text: and

text: can

text: therefore

text: be

text: F

text: stored

text: in

text: a

text: single

text: particle’s

text: internal

text: memory.

text: Subdividing

text: the

text: ﬁnal

text: shape

text: into

text: elements.

text: Recall

text: that

text: a

text: shape

text: is

text: the

text: union

text: of

text: ﬁnitely

text: many

text: edges

text: and

text: faces

text: of

text: G

text: Of

text: course,

text: all

text: edges

text: of

text: G

text: D

text: D

text: have

text: length

text: and

text: all

text: faces

text: of

text: G

text: are

text: equilateral

text: triangles

text: of

text: side

text: length

text: D

text: Let

text: the

text: ﬁnal

text: shape

text: S

text: be

text: of

text: the

text: form

text: S

text: e

text: e

text: t

text: t

text: where

text: F

text: F

text: j

text: j

text: the

text: e

text: ’s

text: are

text: edges

text: of

text: G

text: and

text: the

text: t

text: ’s

text: are

text: (triangular)

text: faces

text: of

text: G

text: i

text: D

text: i

text: D

text: Let

text: be

text: a

text: shape

text: equivalent

text: to

text: S

text: By

text: Lemma

text: the

text: scale

text: of

text: is

text: a

text: F

text: F

text: F

text: positive

text: integer

text: λ

text: (recall

text: that

text: S

text: is

text: minimal).

text: That

text: is,

text: there

text: is

text: a

text: similarity

text: F

text: R

text: R

text: transformation

text: σ

text: such

text: that

text: σ(e

text: is

text: a

text: segment

text: of

text: length

text: λ

text: (i.e.,

text: it

text: i

text: is

text: the

text: union

text: of

text: λ

text: consecutive

text: segments

text: of

text: G

text: contained

text: in

text: and

text: σ(t

text: is

text: D

text: F

text: i

text: an

text: equilateral

text: triangle

text: of

text: side

text: length

text: λ

text: contained

text: in

text: F

text: Let

text: B

text: be

text: the

text: set

text: of

text: vertices

text: of

text: G

text: that

text: are

text: contained

text: in

text: We

text: partition

text: D

text: F

text: B

text: into

text: three

text: families

text: of

text: elements

text: as

text: follows:

text: If

text: v

text: is

text: a

text: vertex

text: of

text: G

text: contained

text: in

text: S

text: then

text: σ(v)

text: constitutes

text: a

text: super-

text: D

text: F

text: vertex

text: of

text: F

text: For

text: every

text: e

text: the

text: vertices

text: of

text: G

text: that

text: are

text: contained

text: in

text: σ(e

text: and

text: are

text: i

text: D

text: i

text: not

text: super-vertices

text: of

text: constitute

text: a

text: super-edge

text: of

text: Similarly,

text: for

text: F

text: F