Regular Triangle Generation on Two-Dimensional Cellular Automata (Logics, Algebras and Languages in Computer Science)

Regular

Triangle

Generation

on

Two-Dimensional

Cellular Automata

渡辺識 大川知

Satoru Watanabe

Satoshi

Okawa

会津大学

The

University of Aizu

1

Introduction

In a dotmatrixmethod,as a pattem or a figure areobtained by dotsonlattices offixedsize,

several dot pattems for eachpattem should be prepared depending

on

the

screen

size. In

recent

years,

as a method which is independent from

screen

size, several methodsto draw

some

pattems

on

a

screen

which consists of two dimensional cellular automata have been

proposed[4][6][9][10]. Komatsu has

proposed

methods todraw

a

square

and

a

rectangle of maximum size in the center of the

screen.

Watanabe and Okawa have proposed another methodtodrawa

square

andadiamond[6],andamethod to drawacircleofradius$r$ atthe

centerof thescreen[9][10].

In this

paper,

wereviewthedefinitions ofpatternandpatterngeneration, andwe

inves-tigatean algorithm to drawa regular triangle of maximum size at the center of the

screen.

First,

we

define two dimensionalpatterns as equivalenceclasses whichare obtained by the

similarity relation definedby movings andscaling ontwo dimensionalplane. Foran $m\cross n$

screen, we definea pattern generation to displaywithappropriatesize (andposition) in the

screen, and we definea pattem generationon the discretizedscreen. Next,westudy a cor-respondence between the discretizedscreenandcellularautomata,andwestudythepattern generationonthe cellularautomata. Furthermore,wereviewabasicsignal propagation anda methodtoobtainamidpointof

one

dimentional cellular

array,

and

we

investigateamethod to drawa linesegment between

any

twopoints and aline

through a

given point and

paral-lel to

a

givenline

as

fundamentaltechniquesfor geometorical drawings. Inthe lastpart,

we

showan algorithmto drawaregulartriangleofmaximumsizeatthecenterofthe

screen.

2

Pattem

Generation

Let$\mathbb{R}$ be a set ofreal numbers, and a two dimensional

plane is denoted by $\mathbb{R}\cross \mathbb{R}$

.

Aset $F\subseteq \mathbb{R}\cross \mathbb{R}$iscalledatwodimensionalfigure, asetof all two dimensionalfiguresis denoted

by$\mathcal{F}$,that is$\mathcal{F}=\{F|F\subseteq \mathbb{R}\cross \mathbb{R}\}$. Afigurewhichisobtained withmoving$P$by$d\in \mathbb{R}\cross \mathbb{R}$

is denotedby $F+d=\{p+d|p\in F\}$, and a figurewhich is obtained with extending$F$by $a(a>0)$times is denotedby$a\cdot F=\{a\cdot p|p\in F\}$

.

We definemappings$S_{d}$ and$Z_{a}$ asfollows

respectively,

$S_{d}(F)=F+d, Z_{a}(F)=a\cdot F.$

We definea similarityrelation $\sim on\mathcal{F}$using$S_{d}$and$Z_{a}$

as

follows. For$F_{1},$ $F_{2}\in \mathcal{F},$

The relation$\sim$isanequivalencerelationontwodimensionalfigures. Wedefine apattem

as aequivalence class using this relation

as

follows. Definition 1

Fora figure$F$,a pattern $[F]$ containing$F$isdefined by

$[F]=\{F’|F’\sim F\},$

andasetof pattern$\mathcal{P}$is defined

by

$\mathcal{P}=\mathcal{F}/\sim=\{P|P=[F], F\in \mathcal{F}\}.$

For

any

$m,n>0,$ $[0, m]\cross[0, n]\subseteq \mathbb{R}\cross \mathbb{R}$is calleda

screen

ofsize$m\cross n$, anditdenotedby

$C_{mxn}$,where $[a, b]$is an interval$\{x|a\leq x\leq b\}.$ Definition2

For

a

pattern$P\in \mathcal{P}$assuming$P=[F]$,generationof$P$

on

$C_{m\cross n}$is toobtain

a

set$D\subseteq C_{m\cross n}$

which satisfies

following

conditions.

1. $\exists a,d$ _{$D=S_{d}Z_{a}(F)$},

2. $\forall e,e’>0$ $S_{d+e}Z_{a+e’}(F)\not\subset C_{m\cross n}.$

Followingdiscussion, we assumethat$m$ and $n$

are

integers forsimplicity. Whenwe

dis-playa figure

on

ascreen,thescreenhastobediscretized, sowediscretize$C_{mxn}$bydividing

thewidthby$m-1$ anddividingthelength by$n-1$

.

In this

process,

for each latticepoint$p,$

a

copy

of small

screen

is set

on

it. The small

screen

at theleftmost and the bottomposition

ofthe discretized screenis$c_{0,0}$,and ascreenwhichispositioned inthe ithpositionfromthe left side of the

array

andjth position from thebottomofthe

array

isdescribedby$c_{i,j}$, that is

$c_{i,j}=C_{[i-0.5,i+0.5]\cross\triangleright-0.5,j+0.5]}.$

Wedefinethescreen$C_{m,n}$whichisobtainedbydiscretizing$C_{m\cross n}$

as

follows,

$C_{m,n}=\{c_{i,j}|0\leq i\leq m,0\leq j\leq n, i,j\in N\}.$

We define a pattern generationonthe discretized

screen

asfollows. Definition3

Forapattern$P=[F]\in \mathcal{P}$,generation of$P$

on

$C_{m,n}$istoobtain thefollowingset$D’\subseteq C_{m,n},$

$D’=\{c_{i,j}|c_{i,j}\cap D\neq\phi\}.$

3

Implementation

with

Cellular

Automata

Two dimensional cellular automata consist of copies of a finite automaton (cell) which are positioned such

as

lattices. Each cell changes its

own

stateto the state which is determined according toits ownstate and the adjacent cells’ states. Wecall the own andadjacent cells neighbors, the function to determine thenext stateaccordingto neighbors’ states is called

a

localmapping. Each cellisexpressedby$a_{i},i$_’whichmeansithrowand the jth column from the

leftmost lowestcell.Theintervalof updatingstateiscalleda step. Formally,atwodimensional

cellular automaton$\mathcal{M}$is definedasfollows,

$\mathcal{M}=(M, Q,\sigma, N)$,

$Q$:

a

setofstates,$\sigma$: alocalmappingfrom$Q\cross Q^{|N|-1}$ to$Q,$ $N$:

a

setofneighbors.Inthis

pa-per, we

investigate the automata whichareplaced$m$cellswidthwaysand$n$ cellslengthways,

wecall them$m\cross n$cellularautomata,andwe

assume

$N$asNeumannneighborhood, namely

consistingof theown,

upper,

lower,rightand left cells. Inaninitialconfigurationof$\mathcal{M},$

$a_{0,0}$

isactive,andthe all other cells

are

in

quiescent.

Byregardingeach cell$a_{i,j}$

as

$c_{i,j}$in thediscretized

screen

$C_{m,n}$,the set$M$

can

beregarded

as

thediscretized

screen

$C_{m,n}$,andthen,

an

$m\cross n$cellular automatoncanbe denoted

as

follows,

$\mathcal{M}=(C_{m,n\prime}Q,\sigma,N)$

.

Therefore,for pattern$P$,

we

regarda problemtogenerate$P$

on

$C_{m,n}$

as

a problemtogenerate

$P$ona cellularautomaton$\mathcal{M}$,thatis,a problem

to construct$\mathcal{M}$ whichgenerates$P.$

To constructsuch$\mathcal{M}$ isto

provide$\sigma$whichspecifies $D’\subseteq C_{m,n}$ ata certain timestarting

from the initial configuration. Here, $D’$ _is specified by letting $a_{i,j}$ be in a special state $s$ if

$a_{i,j}\in D’.$

$M$

Figure1: GenerationofA LineSegment

4

Fundamental Techniques for

Geometorical Drawings

Weexplain sometechniques for geometorical drawings whichare usedin a generationofa regular triangleintwo dimensional cellular automata.

4.1

Basic Signal Propagation

When anext cell of a cell in state $s$ changes its

own

state to $s$ at $k$ steps, we callthe signal

specified by$s$ propagates at speed $1/k$

.

Acell cansend signals

upper,

lower, right, and left

directions.

We

can

obtainacell atthe midpoint of

one

dimentionalcellular

array

by usingdefferent speedofsignals. Acell $A$which is

an

end pointof the

array

sends

a signal

$s$with

speed

1/1

anda signal$t$withspeed1/3totherightdirectionsimultaneously. Acell$B$which is another

endpointof the

array

receives thesignal$s$,and then the cell$B$sendsa signal$\overline{s}$withspeed1/1

totheleft direction. Thesignal$\overline{s}$and the

signal$t$meet atacell$M$,themidpointof the

array.

4.2

Generation

of

A Line

Segment

For

any

cells $P$ and $Q$, we explainhow todrawa linesegmentbetween them inFigure 1 as

follows. $P$sends a signal rightdirectionand $Q$ sends lowerdirection respectively, andthen

obtain the midpoints$M$and$N$of$PH$and$QH$respectively The cell$M$sends

a

signal

upper

direction,and the cell$N$sendsa signalleftdirection,and then the twosignalshit each otherin

cell$R$which is the mid point of the linesegment_$PQ$

.

Repeatingthe above methodrecursively,

weobtain the line segment$PQ.$

4.3

Genaration of

A

Parallel

Line

For

any

cell$P$andaline$l$,

we

explainhow to drawalinethrough$P$andparallelto$l$

as

shown

in Figure2. The cell $P$sends a signal$s$

upper

direction and sends a signal $t$ right direction.

The signal$s$hitsacell$P’$ onthe line$l$,andthen$P’$sendsa signal$s’$ right direction. Thesignal $s’$ hitsacertaincell _$Q$

which is putbeforehand, and then $Q$sendsa signal$u$

upper

direction,

anda signal$v$lower directionsimultaineously.

$P_{\bullet\frac{S\mathcal{V}\downarrow^{Q}}{tV}}s|$

’

Figure 2: Generation ofAParallel Line

$P_{\bullet\frac{.\cdot\cdot\cdot 1_{v’}}{tV}}$

Figure3: Generation ofAParallelLine

Thesignal$u$hitsacell$U$

on

the line$l$and the cell$U$returnsa signal$u’$lowerdirecton. The

signal$v$hitsacell $V$onthetraceof signal $t$,and the cell $V$returns a signal$v’$

upper

directon.

The signal $u’$ and the signal $v’$ meet atacell $R$each other asshown inFigure 3. Drawinga

linebetween the cells$P$and$R$by the method explainedinSec.4.2,weobtain aprallelline$l’.$

5

Regular Triangle

Generation

on

Cellular automata

We investigate a method to generate a regular triangle of maximum size at thecenter ofa given $m\cross n$ cellular automaton. In thefollowing example, we

assume

that for $m>n$, the

maximum

square

$A,$ $B,$ $C$ and $D$ at the center of the screen, the arc, $BD$, quarter of a circle withradius$AB$_andcenter$A$areobtainedbeforehand[6]asshowninFigure4.

Figure4: settingthe

square

and

an arc on

the

screen

5.1

A

Method to Generate

a

Regular Triangl

We explain thegenerationofa regulartriangleatthecenterof the

screen

stepby step.

(1)_{Top Vertices of TheRegularTriangles}

The cell $A$ sends

signals

toright directionand

we

obtain cell$M$which is

a

midpoint of

$AB$

.

The midpointcell$M$ of$AB$

can

be obtainedby the methodexplainedinSec.4.1. Then, a signalwhich is sentupwardfrom$M$

passes

the cell$T$on

arc

$BD$andreaches cell$T’$

on

line

$CD$

.

Here, $T$isatop vertexofa regulartriangle$ABT$and $T’$ isthe top vertex of theregular

triangle

we

will draw.

Figure 5:Top Vertex of The Regular Triangle

(2) _{SidesofThe Regular Triangle}

For$A,$$B$,and$T$,linesegments$AT$and$BT$

can

be obtainedbythemethodexplainedSec.4.2

andaregulartriangle$ABT$_{is obtained.}

$\langle$3)Expansionof The

Figure 6: Sides ofThe Regular Triangle

Figure7: Expansion of TheRegularTriangle

To obtain the regular triangle of maximumsize,

we

should expand the triangle$ABT$_toa trianglewithatopvertex $T’$

.

Bythemethod explained inSec.4.3,Parallellines_to$TA$ and$TB$

whichstart at$T’$canbe obtained_{(Figure7). And}we_{obtain theregular triangle$A’B’T’$atthe}

centerof the

screen.

6

Conclusion

Inthis

paper,

wereview the definitionofa pattem and a pattern generation, andapattem generation on the discretized

screen.

Next, we studied a correspondencebetween the dis-cretized

screen

and cellularautomata, and

we

studied thepattern generation

on

the cellular

automata.Furthermore,we investigate amethodtodrawalinesegmentandaparallellineto

acertainlineas techniquesfor geometoricaldrawings. Inthe last part,weshowanalgorithm

todrawa regular triangleof maximum size at the centerof the

screen.

Drawing a circle

or

an arc

on

two dimensional cellular automata is equal to drawing a circle

or

an arc

on

a

paper

by using a

compass.

Similarly, drawing a line segment on two dimensional cellular automata isequaltodrawing alinesegment

on

a

paper

byusing aruler.

compass

and

a

ruler

can

be drawn also

on

twodimensional cellualrautomata. Acknowledgements

Theauthorsare gratefultotheparticipantsofthesymposiu$m’Logics\cdot Algebras\cdot$Languages

on Computer$Science”for$their commentstoimprove the research anditsapplications. reference

[1]Y.Mizuno,ANewSolution of the Firing SquadSynchronizationProblem forTwo

Dimen-sionalRectangle Arrays, University

_of

Aizu, Grad.Thesis.,March,2005.

[2]M.Teraoka,etal. ADesign of Generalized

Optimum-Time

Firing Squad

Synchronization

Algorithm for Two-Dimensional Cellular Arrays,The 18thAnnual

Conf.ofJapanese

Socicty

for

Artificial

Intelligence,3Hl-04,2004.

[3]A.Settle andJ.Simon,Smaller solutions for the firingsquad,Theoretical ComputerScience,

276,

pp.83-109,

2002.

[4]T.Komatsu, PatternGeneration inTwo DimensionPlane, University

_of

Aizu, Grad.Thesis.,

March,_2008.

[5] S.Wolfram, Two-Dimensional Cellular Automata,

_Journal

_of

Statistical Physics, vo138,

p901-946,March1985.

[6] S.Watanabe and S.Okawa,PatternGeneration

on

Two Dimensional CellularAutomata,

Forumon

_Information

Technology2009,A-023.

[7]

_J.

Mazoyer,A sixstateminimaltime solutiontothefiring squad synchronization problem, TheoreticalComputerScience, vol.50,

pp.183-238,1987.

[8] Y.Nishitani,FiringSynchronizationProblemsfor Patternsspecified bytheSub-General

Position,CellularAutomaton Seminarin UniversityofAizu,$2010.$

[9] S.Watanabe and S.Okawa, Circle Generation

on

Two-Dimensional Cellular Automata,

AlgebraicSystems and Theoretical ComputerScience,RIMS1809,ppl6l-l68, 2012.

[10] S.Watanabe and S.Okawa,Rapid Circle Generation on Two-DimensionalCellular

Au-tomataby $O(r^{2})$ TimeAlgorithm, AlgebraandComputer Science, RIMS 1873,ppl63-l69,

2014.

[11] A.Waksman,Anoptimum solutiontothefiring squad synchronization problem,