EWCG 2005, Eindho en, Ma ch 9–11, 2005
Quad angula ions and 2-Colo a ions
Ca men Co ´es∗¶ Albe o M´a quez†¶ A suhi o Nakamo o‡Jes´us Valenzuela§¶
Abs ac
Any me ic quad angula ion (made by segmen s o
s aigh line) o a poin se in he plane de e mines a
2-colo a ion o he se , such ha edges o he quad an-
gula ion can only join poin s wi h diffe en colo s. In
his wo k we ocus in 2-colo a ions and s udy whe he
hey admi a quad angula ion o no , and whe he ,
gi en wo quad angula ions o he same 2-colo a ion,
i is possible o ca y one in o he o he using some
local ope a ions, called diagonal slides and diagonal
o a ion. Al hough he answe is nega i e in gen-
e al, we can show a e y wide amily o 2-colo a ions,
called onions 2-colo a ion, ha a e quad angulable
and which g aph o quad angula ions is always con-
nec ed.
1 In oduc ion
Gi en a se S, ei he a polygon o a poin se , a quad-
angula ion o Sis a pa i ion o he in e io o S,i
Sis a polygon, o o he con ex hull o S,i Sis a
poin se , in o quad angles (quad ila e als) ob ained
by inse ing edges be ween pai s o poin s (diagonals
be ween e ices o he polygon) such ha he edges
in e sec each o he only a hei end poin s. No all
polygons o poin se s admi quad angula ions, e en
when he quad angles a e no equi ed o be con ex.
In he s udy o fini e elemen me hods and sca e ed
da a in e pola ion, i has ecen ly been shown ha
quad angula ions o poin se s may be mo e desi able
objec s han iangula ions [2]. The quad angula ions
o polygons ha e been also in es iga ed in Compu a-
ional Geome y, mos ly in he con ex o gua ding o
illumina ion p oblems.
F om now on we call a polygon o poin se quad an-
gulable i i admi s a quad angula ion wi hou adding
any addi ional poin (S eine poin ).
The e a e wo diffe en cha ac e iza ions o quad-
angulable poin se s:
∗Depa men o Applied Ma hema ics I, Uni e si y o
Se ille, cco es@us
†Depa men o Applied Ma hema ics I, Uni e si y o
Se ille, [email p o ec ed]
‡Depa men o Ma hema ics, Yokohama Na ional Uni e -
si y, [email p o ec ed]
§Depa men o Ma hema ics, Uni e si y o Ex emadu a
[email p o ec ed]
¶Pa ially suppo ed by MCyT p ojec BFM2001-2474.
•i and only i he e exis s a iangula ion o he
se such ha i s dual g aph con ains a pe ec
ma ching [5].
•i and only i i has an e en numbe o poin s in
i s con ex hull [1].
A quad angula ion is cons uc ed (wi h he addi ion
o a S eine poin o ob ain an e en numbe o poin s
in he con ex hull, i necessa y) in Θ(nlog n).
Fo a mo e comple e ision on quad angula ions we
ecommend Toussain ’s su ey [6].
Gi en a quad angula ion o a poin se in he plane,
i de e mines a 2-colo a ion o he se , such ha edges
o he quad angula ion can only join poin s wi h di -
e en colo s. In his wo k we ocus on 2-colo a ions
and s udy whe he hey admi s a quad angula ion
o no (Sec ion 2), and whe he , gi en wo quad-
angula ions o he same 2-colo a ion, i is possible
o ca y one in o he o he using some local ope a-
ions (Sec ion 3). Finally, in Sec ion 4 we p esen
a e y wide amily o 2-colo a ions, called onions 2-
colo a ion, ha a e quad angulable and which g aph
o quad angula ions is always connec ed.
2 2-colo a ions and quad angula ions
Suppose we ha e a 2-colo a ed poin se Sin he plane
andwewan oknowi i ispossible ocons uc a
quad angula ion o i s con ex hull. A simila condi-
ion o he one gi en by [1] is, in his con ex , e iden :
Lemma 1 A necessa y condi ion o a 2-colo a ion
o a poin se S o admi a quad angula ion ( o be
quad angulable) is ha
1. he numbe o poin s o he con ex hull o Sis
e en; and
2. consecu i e poin s o he hull ha e diffe en colo .
Bu e en when he condi ions o Lemma 1 a e
ulfilled, i is easy o find non-quad angulable 2-
colo a ions, as he one a he le o Figu e 1. In
o de o cons uc a quad angula ion, poin 1 canno
be joined wi h cbecause hen bcan be joined wi h
no black poin bu 1. So we d aw an edge om 1 o
b.Nowbcanno be joined ei he wi h 3 o wi h 4,
because hen co 2, espec i ely, would be isola ed,
and canno be pa o any quad angula ion. Bu i
65
21s Eu opean Wo kshop on Compu a ional Geome y, 2005
we join bwi h 2 he only way o comple e a quad i-
la e al is o ma ch 2 and d, ha lea es 3 isola ed.
I is impo an o ema k ha we a e alking abou
2-colo a ions ins ead se s o poin s. Thus, while he
2-colo a ion a he le o Figu e 1 is no quad angula-
ble, he unde lying poin se is, as we see in he igh
pic u e.
a
b
c
d
1
2
3
4a
b
c
d
1
2
3
4
Figu e 1: The se is ei he quad angulable o no de-
pending on he colo a ion.
No ice ha in he igh pic u e we ha e in e -
changed he colo s o 2 and b, ob aining a se wi h
wo con ex laye s, bo h o hem made by poin s wi h
al e na e colo s. This is a in e es ing configu a ion
since, as we will see in Sec ion 4, i is always quad-
angulable.
3 Diagonal ans o ma ion in quad angula ions
Nakamo o [4], wo king wi h opological quad angu-
la ions on su aces, defines wo diagonal ans o ma-
ions; he diagonal slide and he diagonal o a ion,
ha a e shown in Figu e 2. No e ha , while he di-
agonal slide does no modi y he colo a ion o he se ,
he diagonal o a ion changes he colo o he cen e
o o a ion (because, in o he case, poin s wi h he
same colo a e joined).
Since he same poin se can ha e diffe en col-
o a ions, i is no always possible o change any wo
quad angula ions one in o each o he using only di-
agonal slides. In Figu e 3 wo colo a ions o he
same poin se a e shown; one wi h ou black and
ou whi e poin s, and ano he wi h fi e whi e and
h ee black poin s. Since diagonal slides p ese e col-
o a ions, i is no possible o use hem o ans o m
one quad angula ion in o he o he . Howe e , i is
easy o see ha his can be done using also diagonal
o a ions.
Nakamo o [4] p o ed ha in any closed su ace i is
always possible o ca y one opological quad angula-
ion o a se in o any o he i
1. bo h diagonal slides and o a ions a e allowed; o
2. bo h quad angula ions ha e he same numbe o
poin s o each colo by using only diagonal slides.
diagonal slide
diagonal o a ion
Figu e 2: Diagonal ans o ma ions on quad angula-
ions.
Figu e 3: Quad angula ions o he same se wi h di -
e en colo a ions.
This can be seen in e ms o he connec i i y o
he g aph o quad angula ions. The g aph o quad-
angula ions o a poin se is he g aph ha ing all he
quad angula ions o he se as nodes, and wi h adja-
cen cies co esponding o diagonal slides o diagonal
o a ions. Simila ly, he g aph o quad angula ions o
a 2-colo a ion has as nodes he quad angula ions o
a gi en 2-colo a ion. Since diagonal o a ions change
he 2-colo a ion, he adjacen cies a e de e mined only
by diagonal slides.
Bo h g aph o quad angula ions a e, in gene al, no
connec ed. In Figu e 4, i is shown a 2-colo a ion ha
admi s only wo quad angula ions, being no possible
o pe o m any diagonal slide. I we also allow diago-
nal o a ions i can be shown ha i is no possible o
ans o m one quad angula ion in o he o he . This
gi es ise o he ollowing heo ems:
Theo em 2 The e a e 2-colo a ions wi h discon-
nec ed g aph o quad angula ions.
Theo em 3 The e a e poin se s wi h disconnec ed
g aph o quad angula ions.
66
EWCG 2005, Eindho en, Ma ch 9–11, 2005
Figu e 4: A se wi h disconnec ed g aph o quad an-
gula ions.
Ou example has disconnec ed g aph o quad an-
gula ions bo h as a 2-colo a ion and as a poin se .
An open p oblem is o de e mine i bo h hings al-
ways come oge he , o i he e exi poin se s wi h
connec ed g aph o quad angula ions ha admi 2-
colo a ions which g aph o quad angula ions is no .
In spi e o he g aph o quad angula ions o an a bi-
a y 2-colo a ion is, in gene al, no connec ed, in he
nex sec ion we p esen a wide amily o 2-colo a ions
ha ing his p ope y.
4 Onion 2-colo a ions
I a se o si es ha e an e en numbe o e ices in i s
con ex hull, hen i is quad angulable, and ice- e sa
[1]. This is ew i en o 2-colo a ions in Lemma 1,
bu only as a necessa y condi ion, since we find non-
quad angulable 2-colo a ions ha ulfill i , as he one
we saw in Figu e 1. Bu , wha abou i we ex end
Lemma 1 o he in e io o he se ? I he con ex hull
o he 2-colo a ion ulfill he lemma, we emo e i and
examine he con ex hull o he emaining poin s, and
so on. A 2-colo a ion wi h his p ope y is quad angu-
lable and i s g aph o quad angula ions is connec ed.
We call onion 2-colo a ion o a 2-colo a ion o a
poin se such ha all i s con ex laye s ha e an e en
numbe o poin s wi h al e na e colo s. An onion
laye o an onion 2-colo a ion is he se o edges ha
a e pa o a con ex laye s o he se . We call Oi,
wi h i=0,...,l, o he onion laye s o he onion
2-colo a ion, such ha Oiis inside he polygon de-
fined by Oji i>j(Figu e 5). No e ha he poly-
gon defined by Oldoes no con ain any poin o he
onion 2-colo a ion and ha O0, he con ex hull, is al-
ways included in e e y quad angula ion o he onion
2-colo a ion. By defini ion, he poin s on e e y onion
laye sa is y Lemma 1, ha implies he ollowing e-
sul .
P oposi ion 4 Onion 2-colo a ions a e quad angu-
lable.
The main idea o he p oo is o d aw a iangula-
ion joining poin s be ween wo consecu i e onion lay-
e s. By dele ing he edges ma ching poin s wi h he
O0
O1
Ol
Figu e 5: An onion 2-colo a ion and i s onion laye s.
same colo (Figu e 6) we ob ain a quad angula ion o
he onion 2-colo a ion. I should be no e ha we a e
d awing quad angula ions o con ex polygons wi h a
con ex hole, being he gene al case, decide whe he
a polygon wi h holes admi s a quad angula ion, an
NP-comple e p oblem [3].
Figu e 6: By dele ing he diagonals be ween poin s
wi h he same colo we ob ain quad ila e als.
Bu onion 2-colo a ions a e no he only quad an-
gulable 2-colo a ions, since he e a e quad angulable
2-colo a ions wi h non al e na e colo s in some o i s
con ex laye (Figu e 7) o wi h a odd numbe o poin s
on hem.
Figu e 7: The colo s o he inne con ex laye a e no
al e na e.
In addi ion o be quad angulable, onion 2-
colo a ions ha e connec ed g aph o quad angula-
ions. The p oo is based in he ollowing lemmas:
67
21s Eu opean Wo kshop on Compu a ional Geome y, 2005
Lemma 5 Gi en wo quad angula ions o an onion
2-colo a ion con aining all hei onion laye s, we can
ans o m one in o he o he by only using diagonal
slides.
Lemma 6 Any quad angula ion o an onion 2-
colo a ion can be ca ied in o ano he con aining i s
onion laye s using diagonal slides.
F om hese lemmas i can be easily p o ed he
connec i i y o he g aph o quad angula ions o any
onion 2-colo a ion.
Theo em 7 The g aph o quad angula ions o an
onion 2-colo a ion is non-emp y and connec ed.
In pa icula , i he onion 2-colo a ion ha e only
one laye , we ob ain he ollowing esul :
Co olla y 8 The g aph o quad angula ions o any
quad angulable 2-colo a ion in con ex posi ion is con-
nec ed.
5 Conclusions and open p oblems
Two main ideas can be ex ac ed om his wo k: o
be quad angulable depends on he 2-colo a ion o he
se , and he g aph o quad angula ions o bo h a 2-
colo a ion and a poin se is, in gene al, no con-
nec ed. Howe e , he e exi s a wide amily o 2-
colo a ions, he onion 2-colo a ions, ha a e quad-
angulable and which g aph o quad angula ions is
connec ed.
The e a e se e al ques ions ha appea all along
he p esen wo k. One is o explo e new condi ions
o a 2-colo a ion o be quad angulable, sea ching o
new amilies o quad angulable 2-colo a ions. Rela ed
o he g aph o quad angula ions, an in e es ing ap-
p oach is o s udy he ela ionship, i i exi s, be ween
he connec i i y o he g aph and he colo a ion o
he se . And, since he example p esen ed (Figu e 4)
o a se wi h disconnec ed g aph o quad angula ions
ha e ows wi h un il ou collinea poin s, i would
be con enien o cons uc a new example in gen-
e al posi ion. P obably his implies o wo k wi h se s
wi h g ea e ca dinal and complexi y. Finally, an-
o he line o u u e wo ks is, since hey also admi
2-colo a ions, o ex end his s udy om quad angula-
ions o 2n-la ions o poin se s.
Re e ences
[1] P. Bose and G. Toussain . Cha ac e izing and
efficien ly compu ing quad angula ions o plana
poin se s. Compu e Aided Geome ic Design,
ol. 14, 1997, pp. 763-785.
[2] M. L. Lai and L. L. Schumake . Sca e ed da a
in e pola ion using piecewise polynomials o de-
g ee six. SIAM Nume . Anal., 34(1997), pp.905–
921.
[3] A. Lubiw Decomposing polygonal egions in o
con ex quad ila e als. P oc. Symposium on Com-
pu a ional Geome y, 1985, pp. 97–106
[4] A. Nakamo o. Diagonal ans o ma ions in quad-
angula ions o su aces. J. G aph Theo y,
21:289–299, 1996.
[5] S. Ramaswami, P. Ramos and G. Toussain . Con-
e ing iangula ions o quad angula ions Com-
pu a ional Geome y: Theo y and Applica ions,
Vol. 9, Ma ch 1998, pp. 257-276.
[6] G. Toussain . Quad angula ions o plana se s.
In P oceedings o he 4 h In e na ional Wo kshop
on Algo i hms and Da a S uc u es, pages 218–
227. Sp inge -Ve lag, 1995.
68