text: every side s of every triangle t , the vertices of G that are contained i D in σ(s) and are not in a super-vertex of S(cid:48) constitute a super-edge of F S(cid:48) . F • For every t , the vertices of G that are contained in σ(t ) and are i D i not super-vertices of S(cid:48) or contained in super-edges of S(cid:48) constitute F F a super-triangle of S(cid:48) . F Observe that every super-vertex of S(cid:48) is a vertex of G , every super-edge F D of S(cid:48) is a set of λ − 1 consecutive vertices of G , and every super-triangle F D of S(cid:48) is a set of (λ − 1)(λ − 2)/2 vertices of G whose convex hull is an F D equilateral triangle of side length max{0, λ − 3}. There is a small exception to our previous deﬁnition of element. Suppose that the system executing the role assignment phase has k > 1 Leaders, and therefore S is unbreakably k-symmetric. Suppose that S(cid:48) is unbreakably F F k-symmetric, as well: so, by Lemma 3, λ is not a multiple of k. Finally, suppose that S(cid:48) contains its own center. We have two cases: F • If k = 2, then the center of S(cid:48) is located in the midpoint of a super- F edge e consisting of an even number of vertices of G (see Figure 7a). D So, e is divided by its midpoint into two partial super-edges e(cid:48) and e(cid:48)(cid:48). In this case, e is not an element of S(cid:48) , but e(cid:48) and e(cid:48)(cid:48) are. F • If k = 3, then the center c of S(cid:48) is located in the center of a super- F triangle t consisting of a number of vertices of G that is a multiple D of 3 (see Figure 7b). Let v , v , v be the vertices of t, taken in 1 2 3 counterclockwise order. Let ζ be the ray emanating from c in the direction of the vector −v−→v , and let ζ(cid:48) and ζ(cid:48)(cid:48) be the two rays emanating 1 2 from c and forming angles of 120◦ with ζ. These three rays partition t into three symmetric partial super-triangles t(cid:48), t(cid:48)(cid:48), and t(cid:48)(cid:48)(cid:48) (note that no vertex of G lies on any of these rays). In this case, t is not an D element of S(cid:48) , but t(cid:48), t(cid:48)(cid:48), and t(cid:48)(cid:48)(cid:48) are. F Observe that the set ζ ∪ζ(cid:48) ∪ζ(cid:48)(cid:48) has a 3-fold rotational symmetry, and so does the partition of t into the elements t(cid:48), t(cid:48)(cid:48), and t(cid:48)(cid:48)(cid:48). Given t, diﬀerent particles may disagree on which vertex is v and which vertex is v , and thus they 1 2 may disagree on the orientation of ζ. However, since all particles have the same handedness, they agree on the clockwise direction: so they agree on ζ ∪ ζ(cid:48) ∪ ζ(cid:48)(cid:48), and therefore also on the partition of t into elements. We denote by m the number of super-vertices of S(cid:48) , by m the number v F e of its super-edges, and by m the number of its super-triangles. Of course, t these numbers are independent of the scale of S(cid:48) , and only depend on S . F F 45

text: every

text: side

text: s

text: of

text: every

text: triangle

text: t

text: the

text: vertices

text: of

text: G

text: that

text: are

text: contained

text: i

text: D

text: in

text: σ(s)

text: and

text: are

text: not

text: in

text: a

text: super-vertex

text: of

text: constitute

text: a

text: super-edge

text: of

text: F

text: F

text: For

text: every

text: t

text: the

text: vertices

text: of

text: G

text: that

text: are

text: contained

text: in

text: σ(t

text: and

text: are

text: i

text: D

text: i

text: not

text: super-vertices

text: of

text: or

text: contained

text: in

text: super-edges

text: of

text: constitute

text: F

text: F

text: a

text: super-triangle

text: of

text: F

text: Observe

text: that

text: every

text: super-vertex

text: of

text: is

text: a

text: vertex

text: of

text: G

text: every

text: super-edge

text: F

text: D

text: of

text: is

text: a

text: set

text: of

text: λ

text: consecutive

text: vertices

text: of

text: G

text: and

text: every

text: super-triangle

text: F

text: D

text: of

text: is

text: a

text: set

text: of

text: (λ

text: vertices

text: of

text: G

text: whose

text: convex

text: hull

text: is

text: an

text: F

text: D

text: equilateral

text: triangle

text: of

text: side

text: length

text: λ

text: There

text: is

text: a

text: small

text: exception

text: to

text: our

text: previous

text: deﬁnition

text: of

text: element.

text: Suppose

text: that

text: the

text: system

text: executing

text: the

text: role

text: assignment

text: phase

text: has

text: k

text: Leaders,

text: and

text: therefore

text: S

text: is

text: unbreakably

text: k-symmetric.

text: Suppose

text: that

text: is

text: unbreakably

text: F

text: F

text: k-symmetric,

text: as

text: well:

text: so,

text: by

text: Lemma

text: λ

text: is

text: not

text: a

text: multiple

text: of

text: k.

text: Finally,

text: suppose

text: that

text: contains

text: its

text: own

text: center.

text: We

text: have

text: two

text: cases:

text: F

text: If

text: k

text: then

text: the

text: center

text: of

text: is

text: located

text: in

text: the

text: midpoint

text: of

text: a

text: super-

text: F

text: edge

text: e

text: consisting

text: of

text: an

text: even

text: number

text: of

text: vertices

text: of

text: G

text: (see

text: Figure

text: D

text: So,

text: e

text: is

text: divided

text: by

text: its

text: midpoint

text: into

text: two

text: partial

text: super-edges

text: and

text: In

text: this

text: case,

text: e

text: is

text: not

text: an

text: element

text: of

text: but

text: and

text: are.

text: F

text: If

text: k

text: then

text: the

text: center

text: c

text: of

text: is

text: located

text: in

text: the

text: center

text: of

text: a

text: super-

text: F

text: triangle

text: t

text: consisting

text: of

text: a

text: number

text: of

text: vertices

text: of

text: G

text: that

text: is

text: a

text: multiple

text: D

text: of

text: (see

text: Figure

text: Let

text: v

text: v

text: v

text: be

text: the

text: vertices

text: of

text: t,

text: taken

text: in

text: counterclockwise

text: order.

text: Let

text: ζ

text: be

text: the

text: ray

text: emanating

text: from

text: c

text: in

text: the

text: direction

text: of

text: the

text: vector

text: −v−→v

text: and

text: let

text: and

text: be

text: the

text: two

text: rays

text: emanating

text: from

text: c

text: and

text: forming

text: angles

text: of

text: with

text: ζ.

text: These

text: three

text: rays

text: partition

text: t

text: into

text: three

text: symmetric

text: partial

text: super-triangles

text: and

text: (note

text: that

text: no

text: vertex

text: of

text: G

text: lies

text: on

text: any

text: of

text: these

text: rays).

text: In

text: this

text: case,

text: t

text: is

text: not

text: an

text: D

text: element

text: of

text: but

text: and

text: are.

text: F

text: Observe

text: that

text: the

text: set

text: ζ

text: has

text: a

text: rotational

text: symmetry,

text: and

text: so

text: does

text: the

text: partition

text: of

text: t

text: into

text: the

text: elements

text: and

text: Given

text: t,

text: diﬀerent

text: particles

text: may

text: disagree

text: on

text: which

text: vertex

text: is

text: v

text: and

text: which

text: vertex

text: is

text: v

text: and

text: thus

text: they

text: may

text: disagree

text: on

text: the

text: orientation

text: of

text: ζ.

text: However,

text: since

text: all

text: particles

text: have

text: the

text: same

text: handedness,

text: they

text: agree

text: on

text: the

text: clockwise

text: direction:

text: so

text: they

text: agree

text: on

text: ζ

text: and

text: therefore

text: also

text: on

text: the

text: partition

text: of

text: t

text: into

text: elements.

text: We

text: denote

text: by

text: m

text: the

text: number

text: of

text: super-vertices

text: of

text: by

text: m

text: the

text: number

text: v

text: F

text: e

text: of

text: its

text: super-edges,

text: and

text: by

text: m

text: the

text: number

text: of

text: its

text: super-triangles.

text: Of

text: course,

text: t

text: these

text: numbers

text: are

text: independent

text: of

text: the

text: scale

text: of

text: and

text: only

text: depend

text: on

text: S

text: F

text: F


text: (as usual), but can also access and update the virtual internal state of the Leader (through an exchange of messages). In the following, to help intu- ition, we will pretend that the Leader is not a virtual particle with a virtual state, but a special particle with its own state that can walk through other particles. As the Leader walks along the directrix, it updates its own internal state, as well as the states of the particles it encounters, much like the head of a Turing machine does as it scans the cells of a tape. So, using the states of the particles located on the directrix, the Leader can compute any function that is computable by a deterministic Turing machine on an blank tape of n/k cells. This already gives the Leader an arsenal of subroutines and techniques with which it can operate on the states of the particles. Say that the Leader wants to perform the same operation on a row of j particles, where j is too large to be stored in the Leader’s internal memory. Suppose that the Leader has already constructed a representation of j, such as a binary code that ﬁts in the states of the ﬁrst O(log j) particles of the directrix. Then, the Leader can come back and decrement this number every time it operates on a particle. When the counter reaches 0, the Leader knows it has to stop. With this technique, the Leader can also “shift” the states of an entire row of j particles by j(cid:48) positions to the left or to the right along the directrix, provided that the numbers j and j(cid:48) are represented in binary in the states of a few particles. It can “swap” the states of two rows of j particles, etc. If the Leader has represented two numbers a and b in binary, it can easily compute the binary representation of their sum or their product with stan- dard techniques, provided that the total number of particles on the directrix is at least O(log(a + b)). Furthermore, given the representation of a num- ber x, the Leader can compute any polynomial function of x with constant coeﬃcients, provided that there are O(log(x)) particles on the directrix. Linearization of the elements. In the role assignment phase, the par- ticles will use a new internal variable, called Role, whose initial value is Undeﬁned. By the end of the phase, each particle will have a well-deﬁned Role. Assigning a Role to a particle essentially means telling the particle which element of S(cid:48) it will contribute to forming in the shape composition F phase. Once a Leader has selected a set of elements of S(cid:48) , it will “label” F each such element with a unique identiﬁer. Since the number of elements is bounded by a constant, the Leader can memorize the correspondence be- tween identiﬁers and elements in its internal memory. Then, it will put an identiﬁer in the Role variable of each particle on its directrix, thus eﬀectively 50

text: (as

label: paragraph

text: usual),

text: but

text: can

text: also

text: access

text: and

text: update

text: the

text: virtual

text: internal

text: state

text: of

text: the

text: Leader

text: (through

text: an

text: exchange

text: of

text: messages).

text: In

text: the

text: following,

text: to

text: help

text: intu-

text: ition,

text: we

text: will

text: pretend

text: that

text: the

text: Leader

text: is

text: not

text: a

text: virtual

text: particle

text: with

text: a

text: virtual

text: state,

text: but

text: a

text: special

text: particle

text: with

text: its

text: own

text: state

text: that

text: can

text: walk

text: through

text: other

text: particles.

text: As

text: the

text: Leader

text: walks

text: along

text: the

text: directrix,

text: it

text: updates

text: its

text: own

text: internal

text: state,

text: as

text: well

text: as

text: the

text: states

text: of

text: the

text: particles

text: it

text: encounters,

text: much

text: like

text: the

text: head

text: of

text: a

text: Turing

text: machine

text: does

text: as

text: it

text: scans

text: the

text: cells

text: of

text: a

text: tape.

text: So,

text: using

text: the

text: states

text: of

text: the

text: particles

text: located

text: on

text: the

text: directrix,

text: the

text: Leader

text: can

text: compute

text: any

text: function

text: that

text: is

text: computable

text: by

text: a

text: deterministic

text: Turing

text: machine

text: on

text: an

text: blank

text: tape

text: of

text: n/k

text: cells.

text: This

text: already

text: gives

text: the

text: Leader

text: an

text: arsenal

text: of

text: subroutines

text: and

text: techniques

text: with

text: which

text: it

text: can

text: operate

text: on

text: the

text: states

text: of

text: the

text: particles.

text: Say

text: that

text: the

text: Leader

text: wants

text: to

text: perform

text: the

text: same

text: operation

text: on

text: a

text: row

text: of

text: j

text: particles,

text: where

text: j

text: is

text: too

text: large

text: to

text: be

text: stored

text: in

text: the

text: Leader’s

text: internal

text: memory.

text: Suppose

text: that

text: the

text: Leader

text: has

text: already

text: constructed

text: a

text: representation

text: of

text: j,

text: such

text: as

text: a

text: binary

text: code

text: that

text: ﬁts

text: in

text: the

text: states

text: of

text: the

text: ﬁrst

text: O(log

text: j)

text: particles

text: of

text: the

text: directrix.

text: Then,

text: the

text: Leader

text: can

text: come

text: back

text: and

text: decrement

text: this

text: number

text: every

text: time

text: it

text: operates

text: on

text: a

text: particle.

text: When

text: the

text: counter

text: reaches

text: the

text: Leader

text: knows

text: it

text: has

text: to

text: stop.

text: With

text: this

text: technique,

text: the

text: Leader

text: can

text: also

text: “shift”

text: the

text: states

text: of

text: an

text: entire

text: row

text: of

text: j

text: particles

text: by

text: positions

text: to

text: the

text: left

text: or

text: to

text: the

text: right

text: along

text: the

text: directrix,

text: provided

text: that

text: the

text: numbers

text: j

text: and

text: are

text: represented

text: in

text: binary

text: in

text: the

text: states

text: of

text: a

text: few

text: particles.

text: It

text: can

text: “swap”

text: the

text: states

text: of

text: two

text: rows

text: of

text: j

text: particles,

text: etc.

text: If

text: the

text: Leader

text: has

text: represented

text: two

text: numbers

text: a

text: and

text: b

text: in

text: binary,

text: it

text: can

text: easily

text: compute

text: the

text: binary

text: representation

text: of

text: their

text: sum

text: or

text: their

text: product

text: with

text: stan-

text: dard

text: techniques,

text: provided

text: that

text: the

text: total

text: number

text: of

text: particles

text: on

text: the

text: directrix

text: is

text: at

text: least

text: O(log(a

text: b)).

text: Furthermore,

text: given

text: the

text: representation

text: of

text: a

text: num-

text: ber

text: x,

text: the

text: Leader

text: can

text: compute

text: any

text: polynomial

text: function

text: of

text: x

text: with

text: constant

text: coeﬃcients,

text: provided

text: that

text: there

text: are

text: O(log(x))

text: particles

text: on

text: the

text: directrix.

text: Linearization

text: of

text: the

text: elements.

text: In

text: the

text: role

text: assignment

text: phase,

text: the

text: par-

text: ticles

text: will

text: use

text: a

text: new

text: internal

text: variable,

text: called

text: Role,

text: whose

text: initial

text: value

text: is

text: Undeﬁned.

text: By

text: the

text: end

text: of

text: the

text: phase,

text: each

text: particle

text: will

text: have

text: a

text: well-deﬁned

text: Role.

text: Assigning

text: a

text: Role

text: to

text: a

text: particle

text: essentially

text: means

text: telling

text: the

text: particle

text: which

text: element

text: of

text: it

text: will

text: contribute

text: to

text: forming

text: in

text: the

text: shape

text: composition

text: F

text: phase.

text: Once

text: a

text: Leader

text: has

text: selected

text: a

text: set

text: of

text: elements

text: of

text: it

text: will

text: “label”

text: F

text: each

text: such

text: element

text: with

text: a

text: unique

text: identiﬁer.

text: Since

text: the

text: number

text: of

text: elements

text: is

text: bounded

text: by

text: a

text: constant,

text: the

text: Leader

text: can

text: memorize

text: the

text: correspondence

text: be-

text: tween

text: identiﬁers

text: and

text: elements

text: in

text: its

text: internal

text: memory.

text: Then,

text: it

text: will

text: put

text: an

text: identiﬁer

text: in

text: the

text: Role

text: variable

text: of

text: each

text: particle

text: on

text: its

text: directrix,

text: thus

text: eﬀectively


text: that lives in an abstract graph G. A particle may occupy either one vertex of G or two adjacent vertices: in the ﬁrst case, the particle is said to be contracted; otherwise, it is expanded. Movement. A particle may move through G by performing successive expansion and contraction operations.1 Say v and u are two adjacent vertices of G, and a contracted particle p occupies v. Then, p can expand toward u, thus occupying both v and u. When such an expansion occurs, u is said to be the head of p, and v is its tail. From this position, p can contract again into its head vertex u. As a general rule, when a particle expands toward an adjacent vertex, this vertex is by deﬁnition the particle’s head. An expanded particle cannot expand again unless it contracts ﬁrst, and a contraction always brings a particle to occupy its head vertex. When a particle is contracted, the vertex it occupies is also called the particle’s head; a contracted particle has no tail vertex. If a graph contains several particles, none of its vertices can ever be occupied by more than one particle at the same time. Accordingly, a con- tracted particle cannot expand toward a vertex that is already occupied by another particle. If two or more particles attempt to expand toward the same (unoccupied) vertex at the same time, only one of them succeeds, chosen arbitrarily by an adversarial scheduler (see below). Scheduler. In our model, time is “discrete”, i.e., it is an inﬁnite ordered sequence of instants, called stages, starting with stage 0, and proceeding with stage 1, stage 2, etc. Say that in the graph G there is a set P of particles, which we call a system. At each stage, some particles of P are active, and the others are inactive. We may think of the activation of a particle as an act of an adversarial scheduler, which arbitrarily and unpredictably decides which particles are active at each stage. The only restriction on the scheduler is a bland fairness constraint, requiring that each particle be active for inﬁnitely many stages in total. That is, the scheduler can never keep a particle inactive forever. Sensing and reacting. When a particle is activated for a certain stage, it “looks” at the vertices of G adjacent to its head, discovering if they are currently unoccupied, or if they are head or tail vertices of some particle. If the particle is expanded, it also detects which of these vertices is its own tail; all other particles are indistinguishable (i.e., they are anonymous). Each active particle may then decide to either expand (if it is contracted), contract (if it is expanded), or stay still for that stage. All these operations 1The model in [10] allows a special type of coordinated move called “handover”. Since we will not need our particles to perform this type of move, we omit it from our model. 6 ##LTLine##

text: that

text: lives

text: in

text: an

text: abstract

text: graph

text: G.

text: A

text: particle

text: may

text: occupy

text: either

text: one

text: vertex

text: of

text: G

text: or

text: two

text: adjacent

text: vertices:

text: in

text: the

text: ﬁrst

text: case,

text: the

text: particle

text: is

text: said

text: to

text: be

text: contracted;

text: otherwise,

text: it

text: is

text: expanded.

text: Movement.

text: A

text: particle

text: may

text: move

text: through

text: G

text: by

text: performing

text: successive

text: expansion

text: and

text: contraction

text: Say

text: v

text: and

text: u

text: are

text: two

text: adjacent

text: vertices

text: of

text: G,

text: and

text: a

text: contracted

text: particle

text: p

text: occupies

text: v.

text: Then,

text: p

text: can

text: expand

text: toward

text: u,

text: thus

text: occupying

text: both

text: v

text: and

text: u.

text: When

text: such

text: an

text: expansion

text: occurs,

text: u

text: is

text: said

text: to

text: be

text: the

text: head

text: of

text: p,

text: and

text: v

text: is

text: its

text: tail.

text: From

text: this

text: position,

text: p

text: can

text: contract

text: again

text: into

text: its

text: head

text: vertex

text: u.

text: As

text: a

text: general

text: rule,

text: when

text: a

text: particle

text: expands

text: toward

text: an

text: adjacent

text: vertex,

text: this

text: vertex

text: is

text: by

text: deﬁnition

text: the

text: particle’s

text: head.

text: An

text: expanded

text: particle

text: cannot

text: expand

text: again

text: unless

text: it

text: contracts

text: ﬁrst,

text: and

text: a

text: contraction

text: always

text: brings

text: a

text: particle

text: to

text: occupy

text: its

text: head

text: vertex.

text: When

text: a

text: particle

text: is

text: contracted,

text: the

text: vertex

text: it

text: occupies

text: is

text: also

text: called

text: the

text: particle’s

text: head;

text: a

text: contracted

text: particle

text: has

text: no

text: tail

text: vertex.

text: If

text: a

text: graph

text: contains

text: several

text: particles,

text: of

text: its

text: vertices

text: can

text: ever

text: be

text: occupied

text: by

text: more

text: than

text: one

text: particle

text: at

text: the

text: same

text: time.

text: Accordingly,

text: a

text: con-

text: tracted

text: particle

text: cannot

text: expand

text: toward

text: a

text: vertex

text: that

text: is

text: already

text: occupied

text: by

text: another

text: particle.

text: If

text: two

text: or

text: more

text: particles

text: attempt

text: to

text: expand

text: toward

text: the

text: same

text: (unoccupied)

text: vertex

text: at

text: the

text: same

text: time,

text: only

text: one

text: of

text: them

text: succeeds,

text: chosen

text: arbitrarily

text: by

text: an

text: adversarial

text: scheduler

text: (see

text: below).

text: Scheduler.

text: In

text: our

text: model,

text: time

text: is

text: “discrete”,

text: i.e.,

text: it

text: is

text: an

text: inﬁnite

text: ordered

text: sequence

text: of

text: instants,

text: called

text: stages,

text: starting

text: with

text: stage

text: and

text: proceeding

text: with

text: stage

text: stage

text: etc.

text: Say

text: that

text: in

text: the

text: graph

text: G

text: there

text: is

text: a

text: set

text: P

text: of

text: particles,

text: which

text: we

text: call

text: a

text: system.

text: At

text: each

text: stage,

text: some

text: particles

text: of

text: P

text: are

text: active,

text: and

text: the

text: others

text: are

text: inactive.

text: We

text: may

text: think

text: of

text: the

text: activation

text: of

text: a

text: particle

text: as

text: an

text: act

text: of

text: an

text: adversarial

text: scheduler,

text: which

text: arbitrarily

text: and

text: unpredictably

text: decides

text: which

text: particles

text: are

text: active

text: at

text: each

text: stage.

text: The

text: only

text: restriction

text: on

text: the

text: scheduler

text: is

text: a

text: bland

text: fairness

text: constraint,

text: requiring

text: that

text: each

text: particle

text: be

text: active

text: for

text: inﬁnitely

text: many

text: stages

text: in

text: total.

text: That

text: is,

text: the

text: scheduler

text: can

text: never

text: keep

text: a

text: particle

text: inactive

text: forever.

text: Sensing

text: and

text: reacting.

text: When

text: a

text: particle

text: is

text: activated

text: for

text: a

text: certain

text: stage,

text: it

text: “looks”

text: at

text: the

text: vertices

text: of

text: G

text: adjacent

text: to

text: its

text: head,

text: discovering

text: if

text: they

text: are

text: currently

text: unoccupied,

text: or

text: if

text: they

text: are

text: head

text: or

text: tail

text: vertices

text: of

text: some

text: particle.

text: If

text: the

text: particle

text: is

text: expanded,

text: it

text: also

text: detects

text: which

text: of

text: these

text: vertices

text: is

text: its

text: own

text: tail;

text: all

text: other

text: particles

text: are

text: indistinguishable

text: (i.e.,

text: they

text: are

text: anonymous).

text: Each

text: active

text: particle

text: may

text: then

text: decide

text: to

text: either

text: expand

text: (if

text: it

text: is

text: contracted),

text: contract

text: (if

text: it

text: is

text: expanded),

text: or

text: stay

text: still

text: for

text: that

text: stage.

text: All

text: these

text: operations

text: model

text: in

text: allows

text: a

text: special

text: type

text: of

text: coordinated

text: move

text: called

text: “handover”.

text: Since

text: we

text: will

text: not

text: need

text: our

text: particles

text: to

text: perform

text: this

text: type

text: of

text: move,

text: we

text: omit

text: it

text: from

text: our

text: model.

text: ##LTLine##


text: (a) The chunk is pulled along the arrow. (b) The Double particles expand to cover the super-triangle. Figure 9: Formation of a super-triangle by a chunk containing some Double particles. The Double particles are drawn in white; the other particles in the chunk are drawn in gray. P execute the universal shape formation algorithm with input a representa- tion of the ﬁnal shape S , and if n is at least Θ(m3), then there is a stage, F reached after O(n2) rounds, where P forms a shape equivalent to S . The F total number of moves performed by P up to this stage is O(n2), which is asymptotically optimal; particles no longer move afterwards. Proof. Under these assumptions, Theorems 3–8 apply. So, we can assume that at some stage the particles will be found on k directrices, each contain- 65 ##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## ##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## ##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## ##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## ##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## ##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## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (a)

text: The

text: chunk

text: is

text: pulled

text: along

text: the

text: arrow.

text: (b)

text: The

text: Double

text: particles

text: expand

text: to

text: cover

text: the

text: super-triangle.

text: Figure

text: Formation

label: caption

text: of

text: a

text: super-triangle

text: by

text: a

text: chunk

text: containing

text: some

text: Double

text: particles.

text: The

text: Double

text: particles

text: are

text: drawn

text: in

text: white;

text: the

text: other

text: particles

text: in

text: the

text: chunk

text: are

text: drawn

text: in

text: gray.

text: P

text: execute

text: the

text: universal

text: shape

text: formation

text: algorithm

text: with

text: input

text: a

text: representa-

text: tion

text: of

text: the

text: ﬁnal

text: shape

text: S

text: and

text: if

text: n

text: is

text: at

text: least

text: then

text: there

text: is

text: a

text: stage,

text: F

text: reached

text: after

text: rounds,

text: where

text: P

text: forms

text: a

text: shape

text: equivalent

text: to

text: S

text: The

text: F

text: total

text: number

text: of

text: moves

text: performed

text: by

text: P

text: up

text: to

text: this

text: stage

text: is

text: which

text: is

text: asymptotically

text: optimal;

text: particles

text: no

text: longer

text: move

text: afterwards.

text: Proof.

text: Under

text: these

text: assumptions,

text: Theorems

text: apply.

text: So,

text: we

text: can

text: assume

text: that

text: at

text: some

text: stage

text: the

text: particles

text: will

text: be

text: found

text: on

text: k

text: directrices,

text: each

text: contain-

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: ##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: ##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: ##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: ##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: ##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: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: “full” triangles: when a shape is scaled up, all its triangles are scaled up and become larger full triangles. In this paper, we extended the notion of shape to sets of full triangles and edges: when an edge is scaled up, it remains a row of points. Of course, we can think of shapes that are not modeled by full triangles or edges, but behave like fractals when scaled up. For instance, we may want to include a discretized version of the Sierpinski triangle as a “building block” of our shapes, alongside full triangles and edges. Scaling up a discretized Sierpinski triangle is equivalent to increasing its “resolution”, which causes ﬁner details to appear inside it. Clearly, these scaled-up copies of the discretized Sierpinski triangle are Turing-computable. Generalizing, we can replace our usual notion of geometric similarity between shapes with any Turing-computable equivalence relation ∼. Then, the shape formation problem, with input a shape S , asks to form any shape F S(cid:48) such that S ∼ S(cid:48) . This deﬁnition of shape formation problem includes F F F and greatly generalizes the one studied in this paper, and even applies to scenarios that are not of a geometric nature. Nonetheless, this generalized problem is still solvable by particles, thanks to the technique outlined above. Acknowledgments. This research has been supported in part by the Natu- ral Sciences and Engineering Research Council of Canada under the Discov- ery Grant program, by Prof. Flocchini’s University Research Chair, and by Prof. Yamauchi’s Grant-in-Aid for Scientiﬁc Research on Innovative Areas “Molecular Robotics” (No. 15H00821) of MEXT, Japan and JSPS KAK- ENHI Grant No. JP15K15938. References [1] H. Ando, I. Suzuki, and M. Yamashita. Formation and agreement problems for synchronous mobile robots with limited visibility. In Pro- ceedings of the 10th IEEE Symposium on Intelligent Control, 453–460, 1995. [2] D. Arbuckle and A. Requicha. Self-assembly and self-repair of arbitrary shapes by a swarm of reactive robots: algorithms and simulations. Au- tonomous Robots, 28(2):197–211, 2010. [3] S. Cannon, J.J. Daymude, D. Randall, and A.W. Richa. A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 35th ACM Symposium on Principles of Distributed Computing, 279–288, 2016. 68

text: “full”

text: triangles:

text: when

text: a

text: shape

text: is

text: scaled

text: up,

text: all

text: its

text: triangles

text: are

text: scaled

text: up

text: and

text: become

text: larger

text: full

text: triangles.

text: In

text: this

text: paper,

text: we

text: extended

text: the

text: notion

text: of

text: shape

text: to

text: sets

text: of

text: full

text: triangles

text: and

text: edges:

text: when

text: an

text: edge

text: is

text: scaled

text: up,

text: it

text: remains

text: a

text: row

text: of

text: points.

text: Of

text: course,

text: we

text: can

text: think

text: of

text: shapes

text: that

text: are

text: not

text: modeled

text: by

text: full

text: triangles

text: or

text: edges,

text: but

text: behave

text: like

text: fractals

text: when

text: scaled

text: up.

text: For

text: instance,

text: we

text: may

text: want

text: to

text: include

text: a

text: discretized

text: version

text: of

text: the

text: Sierpinski

text: triangle

text: as

text: a

text: “building

text: block”

text: of

text: our

text: shapes,

text: alongside

text: full

text: triangles

text: and

text: edges.

text: Scaling

text: up

text: a

text: discretized

text: Sierpinski

text: triangle

text: is

text: equivalent

text: to

text: increasing

text: its

text: “resolution”,

text: which

text: causes

text: ﬁner

text: details

text: to

text: appear

text: inside

text: it.

text: Clearly,

text: these

text: scaled-up

text: copies

text: of

text: the

text: discretized

text: Sierpinski

text: triangle

text: are

text: Turing-computable.

text: Generalizing,

text: we

text: can

text: replace

text: our

text: usual

text: notion

text: of

text: geometric

text: similarity

text: between

text: shapes

text: with

text: any

text: Turing-computable

text: equivalence

text: relation

text: Then,

text: the

text: shape

text: formation

text: problem,

text: with

text: input

text: a

text: shape

text: S

text: asks

text: to

text: form

text: any

text: shape

text: F

text: such

text: that

text: S

text: This

text: deﬁnition

text: of

text: shape

text: formation

text: problem

text: includes

text: F

text: F

text: F

text: and

text: greatly

text: generalizes

text: the

text: one

text: studied

text: in

text: this

text: paper,

text: and

text: even

text: applies

text: to

text: scenarios

text: that

text: are

text: not

text: of

text: a

text: geometric

text: nature.

text: Nonetheless,

text: this

text: generalized

text: problem

text: is

text: still

text: solvable

text: by

text: particles,

text: thanks

text: to

text: the

text: technique

text: outlined

text: above.

text: Acknowledgments.

text: This

text: research

text: has

text: been

text: supported

text: in

text: part

text: by

text: the

text: Natu-

text: ral

text: Sciences

text: and

text: Engineering

text: Research

text: Council

text: of

text: Canada

text: under

text: the

text: Discov-

text: ery

text: Grant

text: program,

text: by

text: Prof.

text: Flocchini’s

text: University

text: Research

text: Chair,

text: and

text: by

text: Prof.

text: Yamauchi’s

text: Grant-in-Aid

text: for

text: Scientiﬁc

text: Research

text: on

text: Innovative

text: Areas

text: “Molecular

text: Robotics”

text: (No.

text: of

text: MEXT,

text: Japan

text: and

text: JSPS

text: KAK-

text: ENHI

text: Grant

text: No.

text: References

text: H.

text: Ando,

text: I.

text: Suzuki,

text: and

text: M.

text: Yamashita.

text: Formation

text: and

text: agreement

text: problems

text: for

text: synchronous

text: mobile

text: robots

text: with

text: limited

text: visibility.

text: In

text: Pro-

text: ceedings

text: of

text: the

text: IEEE

text: Symposium

text: on

text: Intelligent

text: Control,

text: D.

text: Arbuckle

text: and

text: A.

text: Requicha.

text: Self-assembly

text: and

text: self-repair

text: of

text: arbitrary

text: shapes

text: by

text: a

text: swarm

text: of

text: reactive

text: robots:

text: algorithms

text: and

text: simulations.

text: Au-

text: tonomous

text: Robots,

text: S.

text: Cannon,

text: J.J.

text: Daymude,

text: D.

text: Randall,

text: and

text: A.W.

text: Richa.

text: A

text: Markov

text: chain

text: algorithm

text: for

text: compression

text: in

text: self-organizing

text: particle

text: systems.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: Symposium

text: on

text: Principles

text: of

text: Distributed

text: Computing,


text: A Large-Scale Exploration of Factors Affecting Hand Hygiene Compliance Using Linear Predictive Models ∗ † Michael T. Lash MS, Jason Slater BS, ‡ ∗ Philip M. Polgreen MD MPH, and Alberto Maria Segre PhD ∗ Department of Computer Science, The University of Iowa, Iowa City, IA 52242, { } Email: michael-lash, alberto-segre @uiowa.edu † Gojo Industries, Inc., Akron, OH 44309-0991, Email: slaterj@gojo.com ‡ Department of Internal Medicine, The University of Iowa, Iowa City, IA 52242, Email: philip-polgreen@uiowa.edu Abstract— This large-scale study, consisting of 24.5 million observers may artiﬁcially increase hand hygiene rates tem- hand hygiene opportunities spanning 19 distinct facilities in 10 porarily as the presence of other healthcare workers can induce different states, uses linear predictive models to expose factors peer effects to increase rates [12], [13]. Finally, the number that may affect hand hygiene compliance. We examine the use of human observations possible is quite small in comparison of features such as temperature, relative humidity, inﬂuenza severity, day/night shift, federal holidays and the presence of to the number of opportunities [7], [12]. Several automated new residents in predicting daily hand hygiene compliance. The approaches to monitoring have been proposed [8], [14], [15], results suggest that colder temperatures and federal holidays [16]. Many of these measure hand hygiene upon entering have an adverse effect on hand hygiene compliance rates, and and leaving a patient’s room. The subsequent activation of a that individual cultures and attitudes regarding hand hygiene nearby hand hygiene dispenser is recorded as a hand hygiene exist among facilities. Index Terms—Public healthcare, Hand hygiene, Supervised opportunity fulﬁlled whereas, if no such activation is observed, learning, Linear regression, Event detection the opportunity is not satisﬁed. Such approaches, while not capturing all ﬁve moments of hand hygiene, do provide an I. INTRODUCTION easy and convenient measure of hand hygiene compliance. Healthcare associated infections represent a major cause With automated approaches becoming more common, a more of morbidity and mortality in the United States and other comprehensive picture of hand hygiene adherence should countries [1]. Although many can be treated, these infections emerge, providing new insights into why healthcare workers add greatly to healthcare costs [2]. Furthermore, the emer- abstain from practicing hand hygiene. gence of multidrug resistant bacteria have greatly complicated II. DATA AND METHODS treatment of healthcare associated infections [3], making the A. Hand Hygiene Event Data prevention of these infections even more important. One of the most effective interventions for preventing healthcare associ- Our hand hygiene event data is a proprietary dataset pro- ated infections is hand hygiene [4]. Yet, despite international vided by Gojo Industries. The data were obtained from a programs aimed at increasing hand hygiene [4], [5], [6], rates number of installations consisting of door counter sensors, remain low, less than 50% in most cases [4], [6], [7]. which increment a counter anytime an individual goes in or Because of the importance of hand hygiene in preventing out of a room, and hand hygiene sensors, which increment a healthcare associated infections, infection control programs counter when soap or alcohol rub are dispensed. Additional are encouraged to monitor rates to encourage process im- supporting technology was also installed to collect and record provement [6], [8], [9]. In most cases, hand hygiene mon- timestamped sensor-reported counts. In this paper, we will use itoring is done exclusively by human observers, which are the term dispenser event to designate triggering and use of still considered the gold standard for monitoring [7]. Yet, an instrumented hand hygiene dispenser and door event to human observations are subject to a number of limitations. designate the triggering of a counter sensor located on one of For example, human observers incur high costs and there are the instrumented doors. difﬁculties in standardizing the elicited observations. Also, the A total of 19 facilities in 10 states were outﬁtted with timing and location of observers can greatly affect the diversity sensors; because of privacy concerns, we provide only the state and the quantity of observations [10], [11]. Furthermore, the and CDC Division for each. The facilities comprise a wide distance of observers to healthcare workers under observation range of geographies, spanning both coasts, the midwest, and and the relative busyness of clinical units can adversely affect the south. A total of 1851 door sensors and 639 dispenser sen- the accuracy of human observers [11]. The presence of human sors reported a total of 24,525,806 door events and 6,140,067

text: A

label: title

text: Large-Scale

text: Exploration

text: of

text: Factors

text: Affecting

text: Hand

text: Hygiene

text: Compliance

text: Using

text: Linear

text: Predictive

text: Models

label: author

text: Michael

text: T.

text: Lash

text: MS,

text: Jason

text: Slater

text: BS,

text: Philip

text: M.

text: Polgreen

text: MD

text: MPH,

text: and

text: Alberto

text: Maria

text: Segre

text: PhD

text: Department

text: of

text: Computer

text: Science,

text: The

text: University

text: of

text: Iowa,

text: Iowa

text: City,

text: IA

text: Email:

text: michael-lash,

text: alberto-segre

text: @uiowa.edu

text: Gojo

text: Industries,

text: Inc.,

text: Akron,

text: OH

text: Email:

text: slaterj@gojo.com

text: Department

text: of

text: Internal

text: Medicine,

text: The

text: University

text: of

text: Iowa,

text: Iowa

text: City,

text: IA

text: Email:

text: philip-polgreen@uiowa.edu

text: Abstract—

text: This

label: abstract

text: large-scale

text: study,

text: consisting

text: of

text: million

text: observers

text: may

text: artiﬁcially

text: increase

text: hand

text: hygiene

text: rates

text: tem-

text: hand

text: hygiene

text: opportunities

text: spanning

text: distinct

text: facilities

text: in

text: porarily

text: as

text: the

text: presence

text: of

text: other

text: healthcare

text: workers

text: can

text: induce

text: different

text: states,

text: uses

text: linear

text: predictive

text: models

text: to

text: expose

text: factors

text: peer

text: effects

text: to

text: increase

text: rates

text: Finally,

text: the

text: number

text: that

text: may

text: affect

text: hand

text: hygiene

text: compliance.

text: We

text: examine

text: the

text: use

text: of

text: human

text: observations

text: possible

text: is

text: quite

text: small

text: in

text: comparison

text: of

text: features

text: such

text: as

text: temperature,

text: relative

text: humidity,

text: inﬂuenza

text: severity,

text: day/night

text: shift,

text: federal

text: holidays

text: and

text: the

text: presence

text: of

text: to

text: the

text: number

text: of

text: opportunities

text: Several

text: automated

text: new

text: residents

text: in

text: predicting

text: daily

text: hand

text: hygiene

text: compliance.

text: The

text: approaches

text: to

text: monitoring

text: have

text: been

text: proposed

text: results

text: suggest

text: that

text: colder

text: temperatures

text: and

text: federal

text: holidays

text: Many

text: of

text: these

text: measure

text: hand

text: hygiene

text: upon

text: entering

text: have

text: an

text: adverse

text: effect

text: on

text: hand

text: hygiene

text: compliance

text: rates,

text: and

text: and

text: leaving

text: a

text: patient’s

text: room.

text: The

text: subsequent

text: activation

text: of

text: a

text: that

text: individual

text: cultures

text: and

text: attitudes

text: regarding

text: hand

text: hygiene

text: nearby

text: hand

text: hygiene

text: dispenser

text: is

text: recorded

text: as

text: a

text: hand

text: hygiene

text: exist

text: among

text: facilities.

text: Index

text: Terms—Public

text: healthcare,

text: Hand

text: hygiene,

text: Supervised

text: opportunity

text: fulﬁlled

text: whereas,

text: if

text: no

text: such

text: activation

text: is

text: observed,

text: learning,

text: Linear

text: regression,

text: Event

text: detection

text: the

text: opportunity

text: is

text: not

text: satisﬁed.

text: Such

text: approaches,

text: while

text: not

text: capturing

text: all

text: ﬁve

text: moments

text: of

text: hand

text: hygiene,

text: do

text: provide

text: an

text: I.

text: INTRODUCTION

text: easy

text: and

text: convenient

text: measure

text: of

text: hand

text: hygiene

text: compliance.

text: Healthcare

text: associated

text: infections

text: represent

text: a

text: major

text: cause

text: With

text: automated

text: approaches

text: becoming

text: more

text: common,

text: a

text: more

text: of

text: morbidity

text: and

text: mortality

text: in

text: the

text: United

text: States

text: and

text: other

text: comprehensive

text: picture

text: of

text: hand

text: hygiene

text: adherence

text: should

text: countries

text: Although

text: many

text: can

text: be

text: treated,

text: these

text: infections

text: emerge,

text: providing

text: new

text: insights

text: into

text: why

text: healthcare

text: workers

text: add

text: greatly

text: to

text: healthcare

text: costs

text: Furthermore,

text: the

text: emer-

text: abstain

text: from

text: practicing

text: hand

text: hygiene.

text: gence

text: of

text: multidrug

text: resistant

text: bacteria

text: have

text: greatly

text: complicated

text: II.

text: DATA

text: AND

text: METHODS

text: treatment

text: of

text: healthcare

text: associated

text: infections

text: making

text: the

text: A.

text: Hand

text: Hygiene

text: Event

text: Data

text: prevention

text: of

text: these

text: infections

text: even

text: more

text: important.

text: One

text: of

text: the

text: most

text: effective

text: interventions

text: for

text: preventing

text: healthcare

text: associ-

text: Our

text: hand

text: hygiene

text: event

text: data

text: is

text: a

text: proprietary

text: dataset

text: pro-

text: ated

text: infections

text: is

text: hand

text: hygiene

text: Yet,

text: despite

text: international

text: vided

text: by

text: Gojo

text: Industries.

text: The

text: data

text: were

text: obtained

text: from

text: a

text: programs

text: aimed

text: at

text: increasing

text: hand

text: hygiene

text: rates

text: number

text: of

text: installations

text: consisting

text: of

text: door

text: counter

text: sensors,

text: remain

text: low,

text: less

text: than

text: in

text: most

text: cases

text: which

text: increment

text: a

text: counter

text: anytime

text: an

text: individual

text: goes

text: in

text: or

text: Because

text: of

text: the

text: importance

text: of

text: hand

text: hygiene

text: in

text: preventing

text: out

text: of

text: a

text: room,

text: and

text: hand

text: hygiene

text: sensors,

text: which

text: increment

text: a

text: healthcare

text: associated

text: infections,

text: infection

text: control

text: programs

text: counter

text: when

text: soap

text: or

text: alcohol

text: rub

text: are

text: dispensed.

text: Additional

text: are

text: encouraged

text: to

text: monitor

text: rates

text: to

text: encourage

text: process

text: im-

text: supporting

text: technology

text: was

text: also

text: installed

text: to

text: collect

text: and

text: record

text: provement

text: In

text: most

text: cases,

text: hand

text: hygiene

text: mon-

text: timestamped

text: sensor-reported

text: counts.

text: In

text: this

text: paper,

text: we

text: will

text: use

text: itoring

text: is

text: done

text: exclusively

text: by

text: human

text: observers,

text: which

text: are

text: the

text: term

text: dispenser

text: event

text: to

text: designate

text: triggering

text: and

text: use

text: of

text: still

text: considered

text: the

text: gold

text: standard

text: for

text: monitoring

text: Yet,

text: an

text: instrumented

text: hand

text: hygiene

text: dispenser

text: and

text: door

text: event

text: to

text: human

text: observations

text: are

text: subject

text: to

text: a

text: number

text: of

text: limitations.

text: designate

text: the

text: triggering

text: of

text: a

text: counter

text: sensor

text: located

text: on

text: one

text: of

text: For

text: example,

text: human

text: observers

text: incur

text: high

text: costs

text: and

text: there

text: are

text: the

text: instrumented

text: doors.

text: difﬁculties

text: in

text: standardizing

text: the

text: elicited

text: observations.

text: Also,

text: the

text: A

text: total

text: of

text: facilities

text: in

text: states

text: were

text: outﬁtted

text: with

text: timing

text: and

text: location

text: of

text: observers

text: can

text: greatly

text: affect

text: the

text: diversity

text: sensors;

text: because

text: of

text: privacy

text: concerns,

text: we

text: provide

text: only

text: the

text: state

text: and

text: the

text: quantity

text: of

text: observations

text: Furthermore,

text: the

text: and

text: CDC

text: Division

text: for

text: each.

text: The

text: facilities

text: comprise

text: a

text: wide

text: distance

text: of

text: observers

text: to

text: healthcare

text: workers

text: under

text: observation

text: range

text: of

text: geographies,

text: spanning

text: both

text: coasts,

text: the

text: midwest,

text: and

text: and

text: the

text: relative

text: busyness

text: of

text: clinical

text: units

text: can

text: adversely

text: affect

text: the

text: south.

text: A

text: total

text: of

text: door

text: sensors

text: and

text: dispenser

text: sen-

text: the

text: accuracy

text: of

text: human

text: observers

text: The

text: presence

text: of

text: human

text: sors

text: reported

text: a

text: total

text: of

text: door

text: events

text: and


text: Mon. Not. R. Astron. Soc. 000, 1–44 (2015) Printed 30 May 2020 (MN LATEX style ﬁle v2.2) Stellar Disc Truncations and Extended Haloes in Face-on Spiral Galaxies S. P. C. Peters1, P. C. van der Kruit1(cid:63), J. H. Knapen2,3, I. Trujillo2,3, J. Fliri2,3, M. Cisternas2, L. S. Kelvin2,3,4 1Kapteyn Astronomical Institute, University of Groningen, P.O.Box 800, 9700AV Groningen, the Netherlands 2Instituto de Astrof´ısica de Canarias, V´ıaLa´ctea, E-38205 La Laguna, Tenerife, Spain 3Departamento de Astrof´ısica, Universidad de La Laguna, E-38205 La Laguna, Tenerife, Spain 4Institut fu¨r Astro- und Teilchenphysik, Universita¨t Innsbruck, Technikerstraße 25’ 6020 Innsbruck, Austria Accepted 2015 month xx. Received 2015 Month xx; in original form 2015 Month xx ABSTRACT We use data from the IAC Stripe82 Legacy Project to study the surface photome- try of 22 nearby, face-on to moderately inclined spiral galaxies. The reprocessed and (cid:48) (cid:48) (cid:48) combined Stripe 82 g , r and i images allow us to probe the galaxy down to 29-30 (cid:48) r -magnitudes/arcsec2 and thus reach into the very faint outskirts of the galaxies. Truncations are found in three galaxies. An additional 15 galaxies are found to have an apparent extended stellar halo. Simulations show that the scattering of light from the inner galaxy by the Point Spread Function (PSF) can produce faint structures resembling haloes, but this eﬀect is insuﬃcient to fully explain the observed haloes. The presence of these haloes and of truncations is mutually exclusive, and we argue that the presence of a stellar halo and/or light scattered by the PSF can hide trun- cations. Furthermore, we ﬁnd that the onset of the stellar halo and the truncations scales tightly with galaxy size. Interestingly, the fraction of light does not correlate with dynamic mass. Nineteen galaxies are found to have breaks in their proﬁles, the radius of which also correlates with galaxy size. Key words: galaxies: photometry, galaxies: spiral, galaxies: structure 1 INTRODUCTION tegration through face-on and moderately inclined galax- ies. Due to this, the expected surface brightness at four Truncations in edge-on stellar discs were ﬁrst discovered scalelengths is about 26 B-mag arcsec2, only a few per- by van der Kruit (1979), who noted that the radial extent of cent of the dark sky (van der Kruit & Searle 1981a, 1982). these galaxies did not grow with deeper photographic expo- In recent times, various studies on inclined or face-on sam- sures, in contrast with the vertical extent. Truncations are ples have been performed looking for such truncations. For very sharp, with scalelengths of less than 1 kpc and typically comparison with the van der Kruit & Searle systems one occur at around four to ﬁve times the exponential scale- would ﬁrst concentrate on non-barred late-type systems. length of the inner disc (van der Kruit & Searle 1981a,b, Pohlen & Trujillo (2006) studied such a sample of 90 mod- 1982; Fry et al. 1999; de Jong et al. 2007; Barteldrees & erately inclined, late-type systems through ellipse-ﬁtting of Dettmar 1994; Kregel et al. 2002). In a recent extensive isophotes in Sloan Digital Sky Survey (SDSS) data. They analysis of 70 edge-on galaxies in the near-IR, taken from identiﬁed galaxies with truncations, but they also found the Spitzer Survey of Stellar Structure in Galaxies (S4G), cases where the discs continued as unbroken exponentials, Comero´n et al. (2012) concluded that about three out of or even showed an upturn in the outer parts. This latter four thin discs are truncated. behaviour was earlier found in barred early-type galaxies by While truncations in edge-on galaxies have been ob- Erwin et al. (2005), followed up by Erwin et al. (2008) on 66 served for the last 35 years, their face-on counterparts re- barred and by Guti´errez et al. (2011) on 47 unbarred, early- main elusive. This is in part due to shorter line-of-sight in- type galaxies. These studies led to a classiﬁcation system, in which Type I designated exponentials out to the noise level, Type II with a turndown of the proﬁle before that and Type (cid:63) For more information, please contact P.C. van der Kruit by III with an upturn. email at vdkruit@astro.rug.nl. (cid:13) c 2015 RAS

text: Mon.

text: Not.

text: R.

text: Astron.

text: Soc.

text: Printed

text: May

text: (MN

text: LATEX

text: style

text: ﬁle

text: Stellar

text: Disc

text: Truncations

text: and

text: Extended

text: Haloes

text: in

text: Face-on

text: Spiral

text: Galaxies

text: S.

text: P.

text: C.

text: P.

text: C.

text: van

text: der

text: J.

text: H.

text: I.

text: J.

text: M.

text: L.

text: S.

text: Astronomical

text: Institute,

text: University

text: of

text: Groningen,

text: P.O.Box

text: Groningen,

text: the

text: Netherlands

text: de

text: Astrof´ısica

text: de

text: Canarias,

text: V´ıaLa´ctea,

text: La

text: Laguna,

text: Tenerife,

text: Spain

text: de

text: Astrof´ısica,

text: Universidad

text: de

text: La

text: Laguna,

text: La

text: Laguna,

text: Tenerife,

text: Spain

text: fu¨r

text: Astro-

text: und

text: Teilchenphysik,

text: Universita¨t

text: Innsbruck,

text: Technikerstraße

text: Innsbruck,

text: Austria

text: Accepted

label: date

text: month

text: xx.

text: Received

text: Month

text: xx;

text: in

text: original

text: form

text: Month

text: xx

text: ABSTRACT

text: We

text: use

text: data

text: from

text: the

text: IAC

text: Legacy

text: Project

text: to

text: study

text: the

text: surface

text: photome-

text: try

text: of

text: nearby,

text: face-on

text: to

text: moderately

text: inclined

text: spiral

text: galaxies.

text: The

text: reprocessed

text: and

text: combined

text: Stripe

text: g

text: r

text: and

text: i

text: images

text: allow

text: us

text: to

text: probe

text: the

text: galaxy

text: down

text: to

text: r

text: and

text: thus

text: reach

text: into

text: the

text: very

text: faint

text: outskirts

text: of

text: the

text: galaxies.

text: Truncations

text: are

text: found

text: in

text: three

text: galaxies.

text: An

text: additional

text: galaxies

text: are

text: found

text: to

text: have

text: an

text: apparent

text: extended

text: stellar

text: halo.

text: Simulations

text: show

text: that

text: the

text: scattering

text: of

text: light

text: from

text: the

text: inner

text: galaxy

text: by

text: the

text: Point

text: Spread

text: Function

text: (PSF)

text: can

text: produce

text: faint

text: structures

text: resembling

text: haloes,

text: but

text: this

text: eﬀect

text: is

text: insuﬃcient

text: to

text: fully

text: explain

text: the

text: observed

text: haloes.

text: The

text: presence

text: of

text: these

text: haloes

text: and

text: of

text: truncations

text: is

text: mutually

text: exclusive,

text: and

text: we

text: argue

text: that

text: the

text: presence

text: of

text: a

text: stellar

text: halo

text: and/or

text: light

text: scattered

text: by

text: the

text: PSF

text: can

text: hide

text: trun-

text: cations.

text: Furthermore,

text: we

text: ﬁnd

text: that

text: the

text: onset

text: of

text: the

text: stellar

text: halo

text: and

text: the

text: truncations

text: scales

text: tightly

text: with

text: galaxy

text: size.

text: Interestingly,

text: the

text: fraction

text: of

text: light

text: does

text: not

text: correlate

text: with

text: dynamic

text: mass.

text: Nineteen

text: galaxies

text: are

text: found

text: to

text: have

text: breaks

text: in

text: their

text: proﬁles,

text: the

text: radius

text: of

text: which

text: also

text: correlates

text: with

text: galaxy

text: size.

text: Key

text: words:

text: galaxies:

text: photometry,

text: galaxies:

text: spiral,

text: galaxies:

text: structure

text: INTRODUCTION

text: tegration

text: through

text: face-on

text: and

text: moderately

text: inclined

text: galax-

text: ies.

text: Due

text: to

text: this,

text: the

text: expected

text: surface

text: brightness

text: at

text: four

text: Truncations

text: in

text: edge-on

text: stellar

text: discs

text: were

text: ﬁrst

text: discovered

text: scalelengths

text: is

text: about

text: B-mag

text: only

text: a

text: few

text: per-

text: by

text: van

text: der

text: Kruit

text: who

text: noted

text: that

text: the

text: radial

text: extent

text: of

text: cent

text: of

text: the

text: dark

text: sky

text: (van

text: der

text: Kruit

text: Searle

text: these

text: galaxies

text: did

text: not

text: grow

text: with

text: deeper

text: photographic

text: expo-

text: In

text: recent

text: times,

text: various

text: studies

text: on

text: inclined

text: or

text: face-on

text: sam-

text: sures,

text: in

text: contrast

text: with

text: the

text: vertical

text: extent.

text: Truncations

text: are

text: ples

text: have

text: been

text: performed

text: looking

text: for

text: such

text: truncations.

text: For

text: very

text: sharp,

text: with

text: scalelengths

text: of

text: less

text: than

text: kpc

text: and

text: typically

text: comparison

text: with

text: the

text: van

text: der

text: Kruit

text: Searle

text: systems

text: one

text: occur

text: at

text: around

text: four

text: to

text: ﬁve

text: times

text: the

text: exponential

text: scale-

text: would

text: ﬁrst

text: concentrate

text: on

text: non-barred

text: late-type

text: systems.

text: length

text: of

text: the

text: inner

text: disc

text: (van

text: der

text: Kruit

text: Searle

text: Pohlen

text: Trujillo

text: studied

text: such

text: a

text: sample

text: of

text: mod-

text: Fry

text: et

text: al.

text: de

text: Jong

text: et

text: al.

text: Barteldrees

text: erately

text: inclined,

text: late-type

text: systems

text: through

text: ellipse-ﬁtting

text: of

text: Dettmar

text: Kregel

text: et

text: al.

text: In

text: a

text: recent

text: extensive

text: isophotes

text: in

text: Sloan

text: Digital

text: Sky

text: Survey

text: (SDSS)

text: data.

text: They

text: analysis

text: of

text: edge-on

text: galaxies

text: in

text: the

text: near-IR,

text: taken

text: from

text: identiﬁed

text: galaxies

text: with

text: truncations,

text: but

text: they

text: also

text: found

text: the

text: Spitzer

text: Survey

text: of

text: Stellar

text: Structure

text: in

text: Galaxies

text: cases

text: where

text: the

text: discs

text: continued

text: as

text: unbroken

text: exponentials,

text: Comero´n

text: et

text: al.

text: concluded

text: that

text: about

text: three

text: out

text: of

text: or

text: even

text: showed

text: an

text: upturn

text: in

text: the

text: outer

text: parts.

text: This

text: latter

text: four

text: thin

text: discs

text: are

text: truncated.

text: behaviour

text: was

text: earlier

text: found

text: in

text: barred

text: early-type

text: galaxies

text: by

text: While

text: truncations

text: in

text: edge-on

text: galaxies

text: have

text: been

text: ob-

text: Erwin

text: et

text: al.

text: followed

text: up

text: by

text: Erwin

text: et

text: al.

text: on

text: served

text: for

text: the

text: last

text: years,

text: their

text: face-on

text: counterparts

text: re-

text: barred

text: and

text: by

text: Guti´errez

text: et

text: al.

text: on

text: unbarred,

text: early-

text: main

text: elusive.

text: This

text: is

text: in

text: part

text: due

text: to

text: shorter

text: line-of-sight

text: in-

text: type

text: galaxies.

text: These

text: studies

text: led

text: to

text: a

text: classiﬁcation

text: system,

text: in

text: which

text: Type

text: I

text: designated

text: exponentials

text: out

text: to

text: the

text: noise

text: level,

text: Type

text: II

text: with

text: a

text: turndown

text: of

text: the

text: proﬁle

text: before

text: that

text: and

text: Type

text: For

text: more

text: information,

text: please

text: contact

text: P.C.

text: van

text: der

text: Kruit

text: by

text: III

text: with

text: an

text: upturn.

text: email

text: at

text: vdkruit@astro.rug.nl.

text: c

text: RAS


text: 4 S. P. C. Peters et al. ◦ Galaxy Type Mb MB vrad [km/s] D [Mpc] i [ ] Vrot [km/s] PA [θ] IC1515 Sb 14.4 -20.5 6560 93.1 26.8 332.6 252.3 IC1516 Sbc 14.2 -21.0 7170 101.7 17.6 418.7 202.1 NGC450 SABc 12.8 -19.3 1729 24.5 45.5 146.4 171.6 NGC493 Sc 13 -19.7 2277 32.3 72.9 158.2 148.9 NGC497 SBbc 13.8 -21.6 7932 112.5 65.4 302.9 219.5 NGC799 SBa 14.2 -20.5 5730 81.3 28.9 341.8 159.1 NGC856 Sa 14.2 -20.5 5786 82.1 38 284.2 113.6 NGC941 SABc 13 -18.8 1557 22.1 44.7 123.0 254.1 NGC1090 Sbc 12.6 -20.4 2660 37.7 64.4 188.2 190.6 NGC7398 Sa 14.8 -19.6 4735 67.2 48.4 235.4 163.1 UGC139 SABc 14.5 -19.3 3899 55.3 64.6 172.7 170.6 UGC272 SABc 15.2 -18.5 3821 54.2 67.2 133.8 219.0 UGC651 Sc 16.1 -18.4 5064 71.8 68.9 256.3 UGC866 Sd 15.6 -16.5 1710 24.3 71.2 80.3 146.9 UGC1934 Sbc 15.5 -20.8 11996 170.2 74.7 297.5 200.4 UGC2081 SABc 15 -17.8 2522 35.8 54.7 122.0 163.1 UGC2311 Sb 14.1 -21.1 6901 97.9 30.9 343.0 170.2 UGC2319 Sc 15.5 -19.7 6827 96.8 72.8 202.6 45.5 UGC2418 SABb 15.1 -20.2 6671 94.6 46.7 205.4 184.5 UGC12183 Sbc 15.5 -19.0 4728 67.1 54.8 164.6 120.4 UGC12208 Scd 15.2 -18.7 3342 47.4 42.8 156.2 UGC12709 SABm 14.4 -18.6 2700 38.3 51.8 103.7 229.7 Table 1. Sample properties. Morphological type, apparent magnitude Mb, absolute magnitude MB (both in B-band), radial velocity vrad and maximum rotational velocity Vrot from HYPERLeda, based on width at 20 of the HI ﬂux and corrected based on the inclination from this work (Paturel et al. 2003; Springob et al. 2005; Theureau et al. 1998; Meyer et al. 2004). Distance D from NED, based on · Virgo + GA + Shapley and assuming H0 70.5 km/sec Mpc, Ωmatter 0.27 and Ωvacuum 0.73. The absolute magnitude has been distance corrected using this distance and has been corrected for foreground extinction based on Schlaﬂy & Finkbeiner (2011). Inclination i this work. No rotational velocities are available in the literature for UGC651 and UGC12208. Position Angle PA based on this work. 3 PROFILE EXTRACTION tude it counts the number of pixels N that are equal to or brighter than the current magnitude. We make the reason- In this section we discuss our four methods to extract able assumption that the galaxy forms an ellipse on the sky, radial surface brightness proﬁles from the observed distribu- with a shape based on the 25th magnitude parameters from tions. The ﬁrst three have been used before, but the fourth the ellipse ﬁtting in Section . Since each pixel covers a small one is new. (cid:48)(cid:48) × (cid:48)(cid:48) surface on the sky of 0.396 0.396 , we can use the total 3.1 Ellipse Fitting amount of pixels N belonging to brightness µ to estimate a We use the IRAF package stsdas.ellipse (Jedrzejewski total surface S and from there use the ellipse to estimate an 1987; Busko 1996) to extract ellipse proﬁles from the data. equivalent (major axis) radius R. In a ﬁrst pass, the package was allowed to run with the posi- Peters et al. (2017) extensively tested the technique on tion angle and inclination as free parametres. This was done a sub-sample of 29 galaxies deﬁned previously by Pohlen & to get the best estimates for the various parameters. We use Trujillo (2006), and found that the results produced by EP the innermost ellipse for the exact position of the center of and ellipse ﬁtting are remarkably similar. At magnitudes the galaxy. The position angle and inclination were mea- near the pixel-to-pixel noise, EP tends to go wrong as it sured from the 25th magnitude ellipse, where we deﬁne the includes noise peaks into the equivalent radius. Peters et al. inclination as i = arccos(b/a), using major and minor axis a (2017) set out to include adaptive smoothing and masking and b. This also gives us the ellipticity e. In the second pass, of the background to avoid this problem, but overall the the central position, position angle and inclination were ﬁxed method was found to work reliably only above the pixel-to- and the method was run again to produce the ﬁnal radial pixel noise limit. proﬁles. In this work, we rotate and centre the original image, based on the positioning as measured using the ellipse pro- 3.2 Equivalent Proﬁles ﬁles in Section . We deﬁne an elliptical mask with a trust The original method for deriving the photometry of radius R set by eye, beyond which the data are set to trust galaxies was the use of the Equivalent Proﬁles method EP blank. Similar to Peters et al. (2017), we again plot our pro- (de Vaucouleurs 1948). The modern-day version of the EP ﬁles out to the radius where over- or under-subtracting the was introduced by Peters et al. (2017), in an attempt to data by two times the uncertainty leads to a deviation of understand the reliability of the ellipse ﬁtting. Compared more than 0.2 magnitudes, compared to the original proﬁle. to the latter, EP works in a fundamentally diﬀerent way. 3.3 Principle Axis Summation Rather than taking a radius R and measuring a correspond- ing average surface brightness µ(R), this method works in In an attempt to recognize the truncations seen in the opposite direction. Starting with the lowest magnitude edge-on galaxies with respect to face-on galaxies better, Pe- in the image and working up from there, for each magni- ters et al. (2017) developed the Principle Axis Summation (cid:13) c 2015 RAS, MNRAS 000, 1–44 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: S.

text: P.

text: C.

text: Peters

text: et

text: al.

label: table

text: Galaxy

text: Type

text: Mb

text: MB

text: vrad

text: [km/s]

text: D

text: [Mpc]

text: i

text: Vrot

text: [km/s]

text: PA

text: [θ]

text: Sb

text: Sbc

text: SABc

text: Sc

text: SBbc

text: SBa

text: Sa

text: SABc

text: Sbc

text: Sa

text: SABc

text: SABc

text: Sc

text: Sd

text: Sbc

text: SABc

text: Sb

text: Sc

text: SABb

text: Sbc

text: Scd

text: SABm

text: Table

text: Sample

text: properties.

text: Morphological

text: type,

text: apparent

text: magnitude

text: Mb,

text: absolute

text: magnitude

text: MB

text: (both

text: in

text: B-band),

text: radial

text: velocity

text: vrad

text: and

text: maximum

text: rotational

text: velocity

text: Vrot

text: from

text: HYPERLeda,

text: based

text: on

text: width

text: at

text: of

text: the

text: HI

text: ﬂux

text: and

text: corrected

text: based

text: on

text: the

text: inclination

text: from

text: this

text: work

text: (Paturel

text: et

text: al.

text: Springob

text: et

text: al.

text: Theureau

text: et

text: al.

text: Meyer

text: et

text: al.

text: Distance

text: D

text: from

text: NED,

text: based

text: on

text: Virgo

text: GA

text: Shapley

text: and

text: assuming

text: km/sec

text: Mpc,

text: Ωmatter

text: and

text: Ωvacuum

text: The

text: absolute

text: magnitude

text: has

text: been

text: distance

text: corrected

text: using

text: this

text: distance

text: and

text: has

text: been

text: corrected

text: for

text: foreground

text: extinction

text: based

text: on

text: Schlaﬂy

text: Finkbeiner

text: Inclination

text: i

text: this

text: work.

text: No

text: rotational

text: velocities

text: are

text: available

text: in

text: the

text: literature

text: for

text: and

text: Position

text: Angle

text: PA

text: based

text: on

text: this

text: work.

text: PROFILE

text: EXTRACTION

text: tude

text: it

text: counts

text: the

text: number

text: of

text: pixels

text: N

text: that

text: are

text: equal

text: to

text: or

text: brighter

text: than

text: the

text: current

text: magnitude.

text: We

text: make

text: the

text: reason-

text: In

text: this

text: section

text: we

text: discuss

text: our

text: four

text: methods

text: to

text: extract

text: able

text: assumption

text: that

text: the

text: galaxy

text: forms

text: an

text: ellipse

text: on

text: the

text: sky,

text: radial

text: surface

text: brightness

text: proﬁles

text: from

text: the

text: observed

text: distribu-

text: with

text: a

text: shape

text: based

text: on

text: the

text: magnitude

text: parameters

text: from

text: tions.

text: The

text: ﬁrst

text: three

text: have

text: been

text: used

text: before,

text: but

text: the

text: fourth

text: the

text: ellipse

text: ﬁtting

text: in

text: Section

text: Since

text: each

text: pixel

text: covers

text: a

text: small

text: one

text: is

text: new.

text: surface

text: on

text: the

text: sky

text: of

text: we

text: can

text: use

text: the

text: total

text: Ellipse

text: Fitting

text: amount

text: of

text: pixels

text: N

text: belonging

text: to

text: brightness

text: µ

text: to

text: estimate

text: a

text: We

text: use

text: the

text: IRAF

text: package

text: stsdas.ellipse

text: (Jedrzejewski

text: total

text: surface

text: S

text: and

text: from

text: there

text: use

text: the

text: ellipse

text: to

text: estimate

text: an

text: Busko

text: to

text: extract

text: ellipse

text: proﬁles

text: from

text: the

text: data.

text: equivalent

text: (major

text: axis)

text: radius

text: R.

text: In

text: a

text: ﬁrst

text: pass,

text: the

text: package

text: was

text: allowed

text: to

text: run

text: with

text: the

text: posi-

text: Peters

text: et

text: al.

text: extensively

text: tested

text: the

text: technique

text: on

text: tion

text: angle

text: and

text: inclination

text: as

text: free

text: parametres.

text: This

text: was

text: done

text: a

text: sub-sample

text: of

text: galaxies

text: deﬁned

text: previously

text: by

text: Pohlen

text: to

text: get

text: the

text: best

text: estimates

text: for

text: the

text: various

text: parameters.

text: We

text: use

text: Trujillo

text: and

text: found

text: that

text: the

text: results

text: produced

text: by

text: EP

text: the

text: innermost

text: ellipse

text: for

text: the

text: exact

text: position

text: of

text: the

text: center

text: of

text: and

text: ellipse

text: ﬁtting

text: are

text: remarkably

text: similar.

text: At

text: magnitudes

text: the

text: galaxy.

text: The

text: position

text: angle

text: and

text: inclination

text: were

text: mea-

text: near

text: the

text: pixel-to-pixel

text: noise,

text: EP

text: tends

text: to

text: go

text: wrong

text: as

text: it

text: sured

text: from

text: the

text: magnitude

text: ellipse,

text: where

text: we

text: deﬁne

text: the

text: includes

text: noise

text: peaks

text: into

text: the

text: equivalent

text: radius.

text: Peters

text: et

text: al.

text: inclination

text: as

text: i

text: arccos(b/a),

text: using

text: major

text: and

text: minor

text: axis

text: a

text: set

text: out

text: to

text: include

text: adaptive

text: smoothing

text: and

text: masking

text: and

text: b.

text: This

text: also

text: gives

text: us

text: the

text: ellipticity

text: e.

text: In

text: the

text: second

text: pass,

text: of

text: the

text: background

text: to

text: avoid

text: this

text: problem,

text: but

text: overall

text: the

text: the

text: central

text: position,

text: position

text: angle

text: and

text: inclination

text: were

text: ﬁxed

text: method

text: was

text: found

text: to

text: work

text: reliably

text: only

text: above

text: the

text: pixel-to-

text: and

text: the

text: method

text: was

text: run

text: again

text: to

text: produce

text: the

text: ﬁnal

text: radial

text: pixel

text: noise

text: limit.

text: proﬁles.

text: In

text: this

text: work,

text: we

text: rotate

text: and

text: centre

text: the

text: original

text: image,

text: based

text: on

text: the

text: positioning

text: as

text: measured

text: using

text: the

text: ellipse

text: pro-

text: Equivalent

text: Proﬁles

text: ﬁles

text: in

text: Section

text: We

text: deﬁne

text: an

text: elliptical

text: mask

text: with

text: a

text: trust

text: The

text: original

text: method

text: for

text: deriving

text: the

text: photometry

text: of

text: radius

text: R

text: set

text: by

text: eye,

text: beyond

text: which

text: the

text: data

text: are

text: set

text: to

text: trust

text: galaxies

text: was

text: the

text: use

text: of

text: the

text: Equivalent

text: Proﬁles

text: method

text: EP

text: blank.

text: Similar

text: to

text: Peters

text: et

text: al.

text: we

text: again

text: plot

text: our

text: pro-

text: (de

text: Vaucouleurs

text: The

text: modern-day

text: version

text: of

text: the

text: EP

text: ﬁles

text: out

text: to

text: the

text: radius

text: where

text: over-

text: or

text: under-subtracting

text: the

text: was

text: introduced

text: by

text: Peters

text: et

text: al.

text: in

text: an

text: attempt

text: to

text: data

text: by

text: two

text: times

text: the

text: uncertainty

text: leads

text: to

text: a

text: deviation

text: of

text: understand

text: the

text: reliability

text: of

text: the

text: ellipse

text: ﬁtting.

text: Compared

text: more

text: than

text: magnitudes,

text: compared

text: to

text: the

text: original

text: proﬁle.

text: to

text: the

text: latter,

text: EP

text: works

text: in

text: a

text: fundamentally

text: diﬀerent

text: way.

text: Principle

text: Axis

text: Summation

text: Rather

text: than

text: taking

text: a

text: radius

text: R

text: and

text: measuring

text: a

text: correspond-

text: ing

text: average

text: surface

text: brightness

text: µ(R),

text: this

text: method

text: works

text: in

text: In

text: an

text: attempt

text: to

text: recognize

text: the

text: truncations

text: seen

text: in

text: the

text: opposite

text: direction.

text: Starting

text: with

text: the

text: lowest

text: magnitude

text: edge-on

text: galaxies

text: with

text: respect

text: to

text: face-on

text: galaxies

text: better,

text: Pe-

text: in

text: the

text: image

text: and

text: working

text: up

text: from

text: there,

text: for

text: each

text: magni-

text: ters

text: et

text: al.

text: developed

text: the

text: Principle

text: Axis

text: Summation

text: c

text: RAS,

text: MNRAS

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 32 S. P. C. Peters et al. Figure A12. Results for UGC272. (cid:13) c 2015 RAS, MNRAS 000, 1–44 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: S.

text: P.

text: C.

text: Peters

text: et

text: al.

text: Figure

text: Results

text: for

text: c

text: RAS,

text: MNRAS

text: ##LTFigure##

label: figure

font: default

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 40 S. P. C. Peters et al. Figure A20. Results for UGC12183. (cid:13) c 2015 RAS, MNRAS 000, 1–44 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: S.

text: P.

text: C.

text: Peters

text: et

text: al.

text: Figure

text: Results

text: for

text: c

text: RAS,

text: MNRAS

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: Stellar disc truncations 5 Figure 2. Overview of the background modelling process for the galaxy NGC941. Top left: the original image with objects masked. Top right: the model created for the sky, excluding the galaxy. Lower left: the sky model including the galaxy. Lower right: the ﬁnal image with the sky model subtracted from the observation. In all ﬁgures, the colour scales run from -1.0 to 1.0 ADU. Horizontal and vertical (cid:48)(cid:48) axes are in pixels (one pixel = 0.396 ). North is right, east is top. method PAS. The PAS has been developed to project face- the method to the edge-on galaxy UGC 2584, for which the on galaxies into edge-on galaxies, in the hope that features data are also available in the IAC Stripe 82 Legacy Project, similar to truncations appear. While the method itself was and which we have reduced in the exact same ways as the successful, true truncations remained elusive, due to the face-on galaxies in this sample. The PAS results are shown much shallower nature of the original SDSS data (Peters as the red (top) curve in Figure 3, whereas the blue (lower) et al. 2017). curve demonstrates the surface brightness measured along Similar to the EP, we again rotate and centre the im- the central plane of the galaxy. It is clear that a truncation age, after which we apply the same elliptical blanking mask is visible at a radius of 15 kpc, evident from both methods. at trust radius R . The PAS then partitions the galaxy As noted in Peters et al. (2017), the PAS proﬁles have trust into four quadrants. Quadrants with visible problems, for units of magnitudes/arcsec, as the minor axis summation example a foreground star, were removed. Each quadrant can reach higher values in nearby galaxy with large appar- is then summed onto the major axis, after which the main ent sizes. The result of this is that while the proﬁle itself proﬁle is formed by the median of the accepted quadrants. is reliable, its vertical oﬀset and extent compared to the A dynamic binning algorithm is applied to ensure that the other proﬁles varies. For the sake of comparison, we there- proﬁle has a signal-to-noise ratio of at least two. fore choose to ﬁx the central brightness as seen from the The uncertainty in each point is diﬀerent, due to the PAS at one magnitude lower than the central brightness as varying number of pixels involved in the sum. Similar to measured from the ellipse proﬁles. Peters et al. (2017), for each point, we repeat the PAS tech- 3.4 Rectiﬁed Polar Plots nique many times on randomly drawn samples from the set of background pixels deﬁned in Section , which gives a good One possible reason that truncations in face-on galax- estimate of the uncertainty. ies are in principle diﬃcult to see is that galaxies do not To demonstrate the eﬀect of PAS and the way we expect remain circularly symmetric, but become ragged or lopsided truncations to appear in face-on galaxies, we have applied towards the faint outskirts. Any method of analysis that (cid:13) c 2015 RAS, MNRAS 000, 1–44 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: Stellar

text: disc

text: truncations

text: Figure

text: Overview

text: of

text: the

text: background

text: modelling

text: process

text: for

text: the

text: galaxy

text: Top

text: left:

text: the

text: original

text: image

text: with

text: objects

text: masked.

text: Top

text: right:

text: the

text: model

text: created

text: for

text: the

text: sky,

text: excluding

text: the

text: galaxy.

text: Lower

text: left:

text: the

text: sky

text: model

text: including

text: the

text: galaxy.

text: Lower

text: right:

text: the

text: ﬁnal

text: image

text: with

text: the

text: sky

text: model

text: subtracted

text: from

text: the

text: observation.

text: In

text: all

text: ﬁgures,

text: the

text: colour

text: scales

text: run

text: from

text: to

text: ADU.

text: Horizontal

text: and

text: vertical

text: axes

text: are

text: in

text: pixels

text: (one

text: pixel

text: North

text: is

text: right,

text: east

text: is

text: top.

text: method

text: PAS.

text: The

text: PAS

text: has

text: been

text: developed

text: to

text: project

text: face-

text: the

text: method

text: to

text: the

text: edge-on

text: galaxy

text: UGC

text: for

text: which

text: the

text: on

text: galaxies

text: into

text: edge-on

text: galaxies,

text: in

text: the

text: hope

text: that

text: features

text: data

text: are

text: also

text: available

text: in

text: the

text: IAC

text: Stripe

text: Legacy

text: Project,

text: similar

text: to

text: truncations

text: appear.

text: While

text: the

text: method

text: itself

text: was

text: and

text: which

text: we

text: have

text: reduced

text: in

text: the

text: exact

text: same

text: ways

text: as

text: the

text: successful,

text: true

text: truncations

text: remained

text: elusive,

text: due

text: to

text: the

text: face-on

text: galaxies

text: in

text: this

text: sample.

text: The

text: PAS

text: results

text: are

text: shown

text: much

text: shallower

text: nature

text: of

text: the

text: original

text: SDSS

text: data

text: (Peters

text: as

text: the

text: red

text: (top)

text: curve

text: in

text: Figure

text: whereas

text: the

text: blue

text: (lower)

text: et

text: al.

text: curve

text: demonstrates

text: the

text: surface

text: brightness

text: measured

text: along

text: Similar

text: to

text: the

text: EP,

text: we

text: again

text: rotate

text: and

text: centre

text: the

text: im-

text: the

text: central

text: plane

text: of

text: the

text: galaxy.

text: It

text: is

text: clear

text: that

text: a

text: truncation

text: age,

text: after

text: which

text: we

text: apply

text: the

text: same

text: elliptical

text: blanking

text: mask

text: is

text: visible

text: at

text: a

text: radius

text: of

text: kpc,

text: evident

text: from

text: both

text: methods.

text: at

text: trust

text: radius

text: R

text: The

text: PAS

text: then

text: partitions

text: the

text: galaxy

text: As

text: noted

text: in

text: Peters

text: et

text: al.

text: the

text: PAS

text: proﬁles

text: have

text: trust

text: into

text: four

text: quadrants.

text: Quadrants

text: with

text: visible

text: problems,

text: for

text: units

text: of

text: magnitudes/arcsec,

text: as

text: the

text: minor

text: axis

text: summation

text: example

text: a

text: foreground

text: star,

text: were

text: removed.

text: Each

text: quadrant

text: can

text: reach

text: higher

text: values

text: in

text: nearby

text: galaxy

text: with

text: large

text: appar-

text: is

text: then

text: summed

text: onto

text: the

text: major

text: axis,

text: after

text: which

text: the

text: main

text: ent

text: sizes.

text: The

text: result

text: of

text: this

text: is

text: that

text: while

text: the

text: proﬁle

text: itself

text: proﬁle

text: is

text: formed

text: by

text: the

text: median

text: of

text: the

text: accepted

text: quadrants.

text: is

text: reliable,

text: its

text: vertical

text: oﬀset

text: and

text: extent

text: compared

text: to

text: the

text: A

text: dynamic

text: binning

text: algorithm

text: is

text: applied

text: to

text: ensure

text: that

text: the

text: other

text: proﬁles

text: varies.

text: For

text: the

text: sake

text: of

text: comparison,

text: we

text: there-

text: proﬁle

text: has

text: a

text: signal-to-noise

text: ratio

text: of

text: at

text: least

text: two.

text: fore

text: choose

text: to

text: ﬁx

text: the

text: central

text: brightness

text: as

text: seen

text: from

text: the

text: The

text: uncertainty

text: in

text: each

text: point

text: is

text: diﬀerent,

text: due

text: to

text: the

text: PAS

text: at

text: one

text: magnitude

text: lower

text: than

text: the

text: central

text: brightness

text: as

text: varying

text: number

text: of

text: pixels

text: involved

text: in

text: the

text: sum.

text: Similar

text: to

text: measured

text: from

text: the

text: ellipse

text: proﬁles.

text: Peters

text: et

text: al.

text: for

text: each

text: point,

text: we

text: repeat

text: the

text: PAS

text: tech-

text: Rectiﬁed

text: Polar

text: Plots

text: nique

text: many

text: times

text: on

text: randomly

text: drawn

text: samples

text: from

text: the

text: set

text: of

text: background

text: pixels

text: deﬁned

text: in

text: Section

text: which

text: gives

text: a

text: good

text: One

text: possible

text: reason

text: that

text: truncations

text: in

text: face-on

text: galax-

text: estimate

text: of

text: the

text: uncertainty.

text: ies

text: are

text: in

text: principle

text: diﬃcult

text: to

text: see

text: is

text: that

text: galaxies

text: do

text: not

text: To

text: demonstrate

text: the

text: eﬀect

text: of

text: PAS

text: and

text: the

text: way

text: we

text: expect

text: remain

text: circularly

text: symmetric,

text: but

text: become

text: ragged

text: or

text: lopsided

text: truncations

text: to

text: appear

text: in

text: face-on

text: galaxies,

text: we

text: have

text: applied

text: towards

text: the

text: faint

text: outskirts.

text: Any

text: method

text: of

text: analysis

text: that

text: c

text: RAS,

text: MNRAS

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##