Quad a ic-Time Linea -Space Algo i hms o Gene a ing
O hogonal Polygons wi h a Gi en Numbe o Ve ices ⋆
Ana Paula Tom´as ∗,aand An ´onio Leslie Bajuelos b
aDCC-FC & LIACC, Uni e si y o Po o, Po ugal
bDepa men o Ma hema ics & CEOC - Cen e o Resea ch in Op imiza ion and Con ol, Uni e si y o A ei o, Po ugal
Key wo ds: O hogonal Polygons, Gene a ion, Decomposi ion, Dual G aphs, Mou hs.
1. In oduc ion
This wo k ocus on simple polygons wi hou
holes. The e o e, we call hem jus polygons. Mo e-
o e , “polygon” will some imes mean a polygon
oge he wi h i s in e io . Pdeno es a polygon and
he numbe o i s e lex e ices. A polygon is
o hogonal (o ec ilinea ) i i s edges mee a igh
angles. O’Rou ke [4] has shown ha n= 2 + 4
o e e y n- e ex o hogonal polygon (n-ogon,
o sho ). Gene ic n-ogons may be ob ained om
a pa icula kind o n-ogons, ha we called g id
o hogonal polygons, as illus a ed in Fig. 1.
Fig. 1. Th ee 12-ogons mapped o he same g id 12-ogon.
De ini ion 1 An n-ogon Pis in gene al posi ion
i e e y ho izon al and e ical line con ains a
mos one edge o P, i.e., i Phas no collinea
edges. We call “g id n-ogon” each n-ogon in gene al
posi ion de ined in a n
2×n
2squa e g id.
We assume ha he g id is de ined by ho i-
zon al lines y= 1,...,y =n
2and e ical lines
x= 1,...,x=n
2and ha i s no hwes co ne has
⋆(Ex ended abs ac ) Pa ially unded by LIACC h ough
P og ama de Financiamen o Plu ianual, Funda¸c˜ao pa a a
Ciˆencia e Tecnologia (FCT) and P og ama POSI, and by
CEOC (Uni . o A ei o) h ough P og ama POCTI, FCT,
co- inanced by EC und FEDER.
∗Co esponding au ho
Email add esses: ap @ncc.up.p (Ana Paula Tom´as ),
leslie@ma .ua.p (An ´onio Leslie Bajuelos ).
coo dina es (1,1). Each g id n-ogon has exac ly
one edge in e e y line o he g id.
Each n-ogon no in gene al posi ion may be
mapped o an n-ogon in gene al posi ion by
ǫ-pe u ba ions, o a su icien ly small cons an
ǫ > 0. Hence, we es ic gene a ion o n-ogons
in gene al posi ion. Each n-ogon in gene al posi-
ion is mapped o a unique g id n-ogon h ough
op- o-bo om and le - o- igh sweeping. And,
ecip ocally, gi en a g id n-ogon we may c ea e an
n-ogon ha is an ins ance o i s class by andomly
spacing he g id lines in such a way ha hei
ela i e o de is kep .
1.1. The pape ’s con ibu ion
We p opose wo me hods ha gene a e g id
n-ogons in polynomial ime – In la e-Cu and
In la e-Pas e. The o me was published in [7],
whe e we also ga e implemen a ion de ails, show-
ing ha i equi es linea space in nand uns
in quad a ic ime in a e age. Two p og ams
o gene a ing andom o hogonal polygons, by
O’Rou ke (de eloped o he e alua ion o [5]) and
by Filguei as 1a e men ioned he e. The main
idea o O’Rou ke is o cons uc such a polygon
ia g ow h om a seed cell (i.e., uni squa e) in
a boa d, gluing oge he a gi en numbe o cells
ha a e selec ed andomly using some heu is ics.
Filguei as’ me hod sha es a simila idea hough i
glues ec angles o la ge a eas and allows hem o
o e lap. Nei he o hese me hods allows o con-
ol he inal numbe o e ices o he polygon.
A majo idea in In la e-Pas e is also o glue
1pe sonal communica ion, DCC-LIACC, 2003.
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
ec angles. Ne e heless, i es ic s he posi ions
whe e ec angles may be glued, which ende s he
algo i hm simple and p o ides con ol on he i-
nal numbe o e ices. Fo he la e pu pose, he
In la e ans o ma ion is c ucial. I is possible
o implemen In la e-Pas e so ha i equi es
quad a ic- ime in he wo s -case and linea -space.
Ou me hods may be also adap ed o gene a e
simple o hogonal polygons wi h holes. Indeed,
each hole is an o hogonal polygon wi hou holes.
2. In la e, Cu and Pas e ans o ma ions
Le i= (xi, yi), o i= 1,...,n, be he e ices
o a g id n-ogon P, in CCW o de .
In la e akes a g id n-ogon Pand a pai o
in ege s (p, q) wi h p, q ∈[0,n
2], and yields a new
n- e ex o hogonal polygon ˜
Pwi h e ices ˜ i=
(˜xi,˜yi) gi en by ˜xi=xii xi≤pand ˜xi=xi+ 1
i xi> p, and ˜yi=yii yi≤qand ˜yi=yi+ 1 i
yi> q, o i= 1,...,n. Thus, i augmen s he g id,
c ea ing wo ee lines, x=p+ 1 and y=q+ 1.
In la e-Cu : Le Cbe a uni cell in he in e io
o P, wi h cen e cand no hwes e ex (p, q).
When we apply In la e o Pusing (p, q), cis
mapped o ˜c= (p+ 1, q + 1), ha is he cen e o
in la ed C. The goal o Cu is o in oduce ˜cas
e lex e ex o he polygon. To do ha , i cu s one
ec angle (de ined by ˜cand a e ex ˜ mbelonging
o one o he ou edges sho by he ho izon al and
e ical ays ha emana e om ˜c). We allow such
a ec angle o be cu i i con ains no e ex o ˜
P
excep ˜ m. I no ec angle may be cu , we say ha
Cu ails o C.
So, suppose ha ˜sis he poin whe e one o hese
ays i s in e sec s he bounda y o ˜
P, ha ˜ m
is one o he wo e ices on he edge o ˜
P ha
con ains ˜sand ha he ec angle de ined by ˜cand
˜ mmay be cu . Cu cu s his ec angle om ˜
P
eplacing ˜ mby ˜s, ˜c, ˜s′i his sequence is in CCW
o de (o ˜s′, ˜c, ˜s, o he wise), wi h ˜s′= ˜c+(˜ m−˜s).
We may conclude ha ˜s, ˜c, ˜s′is in CCW o de i ˜s
belongs o he edge ˜ m−1˜ mand in CW o de i i
belongs o ˜ m˜ m+1.Cu always emo es a single
e ex o he g id ogon and in oduces h ee new
ones. Fig. 2 illus a es his echnique. Because Cu
ne e ails i Chas an edge ha is pa o an edge
o P,In la e-Cu may be always applied o P.
4
In la e Cell
Cu 1 Cu 2 Cu 3 Cu 4
3
21
CC
Fig. 2. The wo ec angles de ined by he cen e o C
and he e ices o he le mos e ical edge ((1,1),(1,7))
canno be cu . The e emain he ou possibili ies shown.
In la e-Pas e: We i s imagine he g id
n-ogon me ged in a (n
2+ 2) ×(n
2+ 2) squa e g id,
wi h he op, bo om, le mos and igh mos g id
lines ee. The op line is x= 0 and he le mos
one y= 0, so ha (0,0) is now he no hwes co -
ne o his ex ended g id. Le eH( i) ep esen he
ho izon al edge o P o which ibelongs.
De ini ion 2 Gi en a g id n-ogon Pme ged in o
a(n
2+ 2) ×(n
2+ 2) squa e g id, and a con ex e -
ex io P, he ee s ai case neighbou hood o i,
deno ed by FSN( i), is he la ges s ai case polygon
in his g id ha has ias e ex, does no in e sec
he in e io o Pand i s base edge con ains eH( i).
An example is gi en in Fig. 3.
10
11
12
14 1
2
4
6
3
Fig. 3. A g id n-ogon me ged in o a (n
2+ 2) ×(n
2+ 2)
squa e g id and he ee s ai case neighbou hood o each
o i s con ex e ices, wi h n= 14.
Now, o ans o m Pby In la e-Pas e we
i s ake a con ex e ex io P, selec a cell C
in FSN( i), and apply In la e o Pusing he
no wes co ne (p, q) o C. As be o e, he cen e
o cell Cis mapped o ˜c= (p+ 1, q + 1), which
will now be a con ex e ex o he new polygon.
Pas e glues he ec angle de ined by ˜ iand ˜c
o ˜
P, inc easing he numbe o e ices by wo. I
eH( i)≡ i i+1 hen Pas e emo es ˜ i= (˜xi,˜yi)
and inse s he chain (˜xi, q + 1), ˜c, (p+ 1,˜yi) in i s
place. I eH( i)≡ i−1 i,Pas e eplaces ˜ iby he
sequence (p+ 1,˜yi), ˜c, (˜xi, q + 1). Fig. 4 illus a es
his ans o ma ion. Clea ly, Pas e ne e ails, in
con as o Cu .
Ma ch 25-26, 2004 Se ille (Spain)
10
Fig. 4. The ou g id 14-ogons ha we may cons uc i we
apply In la e-Pas e o he gi en 12-ogon, o ex end he
e ical edge ha ends in e ex 10.
3. In la e-Cu and In la e-Pas e Me hods
We showed in [7] ha e e y g id n-ogon may be
c ea ed om a uni squa e (i.e., he g id 4-ogon) by
applying In la e-Cu ans o ma ions. Now,
we may show he same esul o In la e-Pas e.
A i e a ion k, bo h me hods cons uc a g id
(2k+ 4)-ogon om he g id (2(k−1) + 4)-ogon
ob ained in he p e ious i e a ion, o 1 ≤k≤ .
The In la e-Cu me hod yields a andom g id
n-ogon, i cells and ec angles a e chosen a an-
dom. This is also ue o In la e-Pas e, hough
now o he selec ions o iand o Cin FSN( i).
I is no di icul o see ha bo h In la e-Cu
and In la e-Pas e yield g id ogons. In con as ,
he p oo o hei comple eness is no immedia e,
as sugges ed by he example gi en in Fig. 5.
Fig. 5. The igh mos polygon is he unique g id 16-ogon
ha gi es ise o his 18-ogon, i we apply In la e-Cu .
Be o e we go h ough he p oo , we need o in-
oduce some de ini ions and esul s.
De ini ion 3 Gi en a simple o hogonal polygon
Pwi hou holes, le ΠH(P)be he ho izon al decom-
posi ion o Pin o ec angles ob ained by ex ending
he ho izon al edges inciden o e lex e ices o-
wa ds he in e io o Pun il hey hi i s bounda y.
Each cho d (i.e., edge ex ension) sepa a es exac ly
wo adjacen pieces ( aces), since i makes an ho i-
zon al cu (see e.g. [9]). The dual g aph o ΠH(P)
cap u es he adjacency ela ion be ween pieces o
ΠH(P). I s nodes a e he pieces o ΠH(P) and i s
non-o ien ed edges connec adjacen pieces.
Lemma 4 The dual g aph o ΠH(P)is a ee o
all simple o hogonal polygons Pwi hou holes.
PROOF. This esul ollows om he well-known
Jo dan Cu e Theo em. Suppose he g aph con-
ains a simple cycle F0, F1,...,Fd, F0, wi h d≥2.
Le γ= (γ0,1γ1,2. . . γd,0) be a simple closed cu e
in he in e io o P ha links he cen oids o he
aces F0, F1,...,Fd. Deno e by he e lex e ex
ha de ines he cho d s ha sepa a es F0 om
F1. He e, s is he poin whe e his edge’s ex en-
sion in e sec s he bounda y o P. Ei he o s
would be in he in e io o γ, because γneeds o
c oss he ho izon al line suppo ing s a leas
wice and jus γ0,1c osses s . Bu he in e io o
γis con ained in he in e io o P, and he e exis
poin s in he ex e io o Pin he neighbou hood o
and o s , so ha we achie e a con adic ion. ✷
I is wo h no ing ha he e ical decomposi-
ion ΠV(P) o Pwould ha e iden ical p ope ies.
We shall now p o e P oposi ion 5 ha asse s he
comple eness o In la e-Pas e.
P oposi ion 5 Fo each g id (n+ 2)-ogon, wi h
n≥4, he e is a g id n-ogon ha yields i by
In la e-Pas e.
PROOF. Gi en a g id (n+ 2)-ogon P, we use
Lemma 4 o conclude ha he dual g aph o ΠH(P)
is a ee. Each lea o his ee co esponds o a
ec angle ha could ha e been glued by Pas e o
yield P. Indeed, suppose ha s is he cho d ha
sepa a es a lea F om he es o P. Because g id
ogons a e in gene al posi ion, s is no a e ex o
P. I belongs o he ela i e in e io o an edge o
P. The e ex o ec angle F ha is no adjacen
o s would be ˜cin In la e-Pas e. I we cu F,
we would ob ain an in la ed n-ogon, ha we may
de la e o ge a g id n-ogon ha yields P. The
wo g id lines y=y˜cand x=x˜ca e ee. Clea ly
s is he e ex we called iin he desc ip ion o
In la e-Pas e (mo e accu a ely, s is ˜ i) and c=
(x˜c−1, y˜c−1) ∈F SN( i). ✷
Fo his pape o be sel -con ained, we ecall now
a p oo o he comple eness o In la e-Cu , al-
eady ske ched in [7]. I was inspi ed by wo k abou
con exi ica ion o simple polygons [2,6,8], in pa i-
cula , by a ecen pape by O. Aichholze e al. [1].
I also sha es ideas o a p oo o Meis e s’ Two-
Ea s Theo em [3] by O’Rou ke, hough we we e no
awa e o his when we w o e i . Fig. 6 illus a es
he undamen al ideas.
20 h Eu opean Wo kshop on Compu a ional Geome y
pocke
pocke
A
Fig. 6. The wo le mos g ids show a g id 18-ogon and i s
pocke s. The shaded ec angle A is a lea o he ee associ-
a ed o he e ical pa i ioning o he la ges pocke . The
igh mos polygon is an in la ed g id 16-ogon ha yields
he ep esen ed g id 18-ogon, i Cu emo es ec angle A.
We need some addi ional de ini ions and esul s.
De ini ion 6 Apocke o a noncon ex polygon P
is a maximal sequence o edges o Pdisjoin om
i s con ex hull excep a he endpoin s. The lid is
he line segmen joining i s wo endpoin s.
Any noncon ex polygon Phas a leas one
pocke . Each pocke o an n-ogon, oge he wi h
i s lid, de ines a simple polygon wi hou holes,
ha is almos o hogonal excep o an edge (lid).
I is possible o sligh ly ans o m i o ob ain an
o hogonal polygon, as illus a ed in Fig. 6. We
shall e e o his polygon as an o hogonalized
pocke . Fo e e y o hogonalized pocke Q, i is
easy o see ha he pocke ’s lid is con ained in a
single ec angle o ei he ΠH(Q) o ΠV(Q). Le
Π(Q) ep esen he one whe e he lid is con ained
in a single piece.
P oposi ion 7 Fo each g id (n+ 2)-ogon, he e
is a g id n-ogon ha yields i by In la e-Cu .
PROOF. Gi en a g id (n+ 2)-ogon P, le Qbe
an o hogonalized pocke o P. Necessa ily, Qis in
gene al posi ion. By Lemma 4 he dual g aph o
Π(Q) is a ee. We claim ha a leas one o i s
lea es con ains o is i sel a ec angle ha migh
ha e been emo ed by Cu o yield P. Indeed, he
lea es a e o he wo ollowing o ms.
c
~
~
m
c
~
~
m
The shaded ec angles a e he ones ha migh
ha e been cu . We ha e also ep esen ed he poin s
ha would be ˜ mand ˜cin In la e-Cu . He e, we
mus be ca e ul abou he lea ha has he pocke ’s
lid. Only i he ee consis s o a single node (c. . he
smalles pocke in Fig. 6), may his lea be illed.
Bu , e e y non-degene a ed ee has a leas wo
lea es. Then, in his case he ee has a lea o he
han he one ha con ains he lid. ✷
The concep o mou h [8] was c ucial o each he
cu en o mula ion o Cu . Ac ually, In la e-
Cu is somehow doing he e e se o an algo i hm
gi en by Toussain in [8] ha compu es he con ex
hull o a polygon globbing-up mou hs o succes-
si ely emo e i s conca i ies. Fo o hogonal poly-
gons, we would a he de ine ec angula mou hs.
De ini ion 8 A e lex e ex io an ogon Pis a
ec angula mou h o Pi he in e io o he ec -
angle de ined by i−1and i+1 is con ained in he
ex e io o Pand nei he his ec angle no i s in e-
io con ain e ices o P, excep i−1, iand i+1.
To jus i y he co ec ion o ou echnique, we
obse e ha when we apply Cu o ob ain a g id
(n+ 2)-ogon, he e ex ˜cis always a ec angula
mou h o he esul ing (n+ 2)-ogon. In sum, he
p oo o P oposi ion 7 gi en abo e jus i ies Co ol-
la y 9, which eph ases he One-Mou h Theo em
by Toussain .
Co olla y 9 Each g id n-ogon has a leas one
ec angula mou h, o n≥6.
Re e ences
[1] Aichholze , O., Co ´es, C., Demaine, E. D., Dujmo ic,
V., E ickson, J., Meije , H., O e ma s, M., Palop, B.,
Ramaswawi, S., Toussain , G. T.: Flip u ning polygons.
Disc e e & Compu . Geome y 28 (2002), 231–253.
[2] E d¨os, P.: P oblem numbe 3763. Ame ican
Ma hema ical Mon hly 42 (1935) 627.
[3] Meis e s, G. H.: Polygons ha e ea s. Ame ican
Ma hema ical Mon hly 82 (1975) 648-651.
[4] O’Rou ke, J.: An al e na e p oo o he ec ilinea a
galle y heo em. J. o Geome y 21 (1983) 118–130.
[5] O’Rou ke, J., Pashchenko, I., Tewa i, G.: Pa i ioning
o hogonal polygons in o a ec angles. In P oc. 13 h
Canadian Con e ence on Compu a ional Geome y
(CCCG’01) (2001) 133-136.
[6] Sz.-Nagy, B.: Solu ion o p oblem 3763. Ame ican
Ma hema ical Mon hly 46 (1939) 176–177.
[7] Tom´as, A. P., Bajuelos, A. L.: Gene a ing Random
O hogonal Polygons. To appea in Pos -con e ence
P oceedings o CAEPIA-TTIA’2003, LNAI, Sp inge -
Ve lag (2004).
[8] Toussain , G. T.: Polygons a e an h opomo phic.
Ame ican Ma hema ical Mon hly 122 (1991) 31–35.
[9] U u ia, J.: A galle y and illumina ion p oblems.
In J.-R. Sack and J. U u ia, edi o s, Handbook on
Compu a ional Geome y. Else ie (2000).