Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
SIAM J. DISCRETE MATH.c
2010 Socie y o Indus ial and Applied Ma hema ics
Vol. 24, No. 3, pp. 821–840
TRANSFORMING TRIANGULATIONS ON NONPLANAR
SURFACES∗
C. CORT´
ES†,C.I.GRIMA
†,F.HURTADO
‡,A.M
´
ARQUEZ†,F.SANTOS
§,AND
J. VALENZUELA†
Abs ac . We conside whe he any wo iangula ions o a polygon o a poin se on a nonplana
su ace wi h a gi en me ic can be ans o med in o each o he by a sequence o edge flips. The answe
is nega i e in gene al wi h some ema kable excep ions, such as polygons on he cylinde , and on he
fla o us, and ce ain configu a ions o poin s on he cylinde .
Key wo ds. g aph o iangula ions, iangula ions on su aces, iangula ions o polygons, edge
flip
AMS subjec classi ica ions. 68U05, 52C99, 65D18, 68R10
DOI. 10.1137/070697987
1. In oduc ion. Mos o he p oblems conside ed so a in compu a ional ge-
ome y a e es ic ed o he plane, o o he Euclidean 3-space. Howe e , in many
applica ions i is necessa y o deal wi h inpu da a ha lies on a su ace a he han in
he plane. Recen ly, some wo ks ha e been ocused on sol ing some o he p oblems
a ising in hose cases (c . [8, 13, 16]). This pape is in his ca ego y, s udying he
g aph o iangula ions o a polygon on a su ace.
Pa i ioning geome ic domains in o simple pieces, such as iangles, is a common
s a egy o se e al fields, he fini e elemen me hod being a mos ele an example. In
pa icula , he iangula ion o polygons is an in e media e s ep in many algo i hms
in he a ea o compu a ional geome y.
In many cases, we need o ob ain no only a iangula ion o a gi en egion
bu also a “good” one. Some examples o his asse ion can be ound when i is
desi ed o imp o e he quali y o a g aphic ep esen a ion o o find a “nice” mesh
on a gi en su ace in o de o apply fini e elemen me hods. When he quali y o
he iangula ion wi h espec o some c i e ion is conside ed, and no di ec me hod
o ob aining he op imal iangula ion is known, i is na u al o pe o m ope a ions
ha allow local imp o emen s. The bes -known me hod is he edge flip: when wo
iangles o m a con ex quad ila e al, hei common edge is eplaced by he o he
diagonal o he quad ila e al [2, 6]. This local ans o ma ion, in oduced by Lawson
in [12], can be combined i necessa y wi h me hods such as simula ed annealing o
escape local op ima [7, 11] and has also been used o he pu poses o enume a ion [1].
I also admi s se e al a ia ions [17, 18]. Rega ding he local ope a ion we ha e
jus desc ibed, a basic issue is whe he any wo iangula ions o a domain Dcan
∗Recei ed by he edi o s July 23, 2007; accep ed o publica ion (in e ised o m) May 17, 2010;
published elec onically July 29, 2010.
h p://www.siam.o g/jou nals/sidma/24-3/69798.h ml
†Dep . Ma em´a ica Aplicada I, Uni . de Se illa, Spain (cco [email protected], g [email protected], [email p o ec ed],
jesus @us.es). The esea ch o hese au ho s was pa ially suppo ed by p ojec s MTM2008-05866-
C03-01 and P06-FQM-01649.
‡Dep . Ma em´a ica Aplicada I, Uni . Poli ´ecnica de Ca alunya, Spain ( e an.hu [email protected]).
The esea ch o his au ho was pa ially suppo ed by p ojec s MICINN MTM2009-07242 and Gen.
Ca . 2009SGR1040.
§Dep . Ma em´a icas, Es ad´ıs ica y Compu aci´on, Uni . de Can ab ia, Spain (san os @unican.es).
The esea ch o his au ho was pa ially suppo ed by MTM2008-04699-C03-02.
821
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
822 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
be ans o med in o each o he by means o a sequence o flips. I we define he
iangula ion g aph o Das ha g aph TG(D) ha ing as nodes he iangula ions
o D, wi h adjacencies co esponding o edge flips, hen he abo e ques ion becomes
ob iously whe he TG(D) is a connec ed g aph o no .
I is known ha he g aph o iangula ions o a plana simple polygon o a poin
se wi h n e ices is connec ed and i s diame e is O(n2), which is igh [5]. I is
wo h men ioning ha e en he case o a con ex n-gon Phas been ho oughly s udied
because TG(P) is isomo phic o he o a ion g aph o bina y ees wi h n−2in e nal
nodes [10, 19]. On he sphe e, he si ua ion is essen ially he same as in he plane.
In his wo k we s udy he connec i i y o he iangula ion g aph o simple
polygons and poin se s lying on su aces. Rega ding polygons, we p o e ha o
he cylinde and he o us wi h hei fla me ics he g aph is always connec ed (i
nonemp y). Fo gene al su aces and me ics he si ua ion is usually he opposi e.
E en wo se, o poin se s only ce ain configu a ions on he cylinde ha e a connec ed
g aph o iangula ions.
A his poin i is con enien o cla i y ha wi h he gene al pu pose o ex ending
compu a ional geome y o su aces, i is necessa y o “ ansla e” some o he elemen s
ha usually appea in he plane o he su aces; in ou case, we need o know how
o join a pai o poin s (in o he wo ds, how o ansla e he concep o segmen );
i is known ha , in gene al, he e a e infini ely many geodesics joining wo poin s
bu usually only one wi h he minimal leng h (see [4]). Thus, ollowing he ci ed
wo ks [8, 13, 16] and o he s, his unique minimal geodesic joining a pai o poin s on
a su ace will be called he segmen defined by ha pai o poin s. In wha ollows,
only segmen s be ween pai s o poin s will be conside ed.
Equally some wo ds mus be said abou he su aces, o , mo e conc e ely, abou
he me ic, ha we a e conside ing he e. In gene al, we will s udy he case o he
locally Euclidean su aces ( hose su aces isome ic o he plane in sufficien ly small
egions). These su aces ha e wo ad an ages; on one hand, hey a e gene al enough
in o de o model many p ac ical cases o app oxima e some o he me ics, and,
on he o he , hey ha e an easy ep esen a ion, as we will see in he nex sec ion.
Ne e heless, in sec ion 3 he esul s a e p esen ed in a mo e gene al con ex because
we do no need he fla ep esen a ion o he locally Euclidean su aces (al hough an
al e na i e p oo o he main esul o his sec ion is p esen ed la e in he con ex o
locally Euclidean su aces).
The pape is o ganized as ollows. In sec ion 2 we gi e defini ions and p elimi-
na y esul s, and we es ablish he no a ion ha will be used h oughou his pape .
Sec ion 3 shows one o he main esul s o his pape , which is ha in e e y com-
pac connec ed su ace i is always possible o find a me ic ha admi s polygons
and poin se s wi h nonconnec ed g aphs o iangula ions. Sec ion 4 ocuses on he
connec i i y o he g aph o iangula ions o bo h polygons and poin se s on he
locally Euclidean su aces. We conclude in sec ion 5 wi h some commen s and open
p oblems.
2. P elimina ies. As is known, many p ac ical p oblems canno be modeled
by plana si ua ions, and o he su aces a e equi ed. When we mee phenomena in
which he same configu a ion o gene a ing poin s appea s in cycles, we may analyze
hem wi h he aid o a poin configu a ion on he cylinde o he o us. These a e
wo well-known su aces since, oge he wi h he wis ed cylinde (o infini e M¨obius
s ip) and he Klein bo le, hey easily admi quo ien me ics ha make hem locally
Euclidean. Wi h hese me ics, he g aph o iangula ions o a polygon bo h on he
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 823
cylinde and on he o us is connec ed, al hough his ac does no hold on he o he
wo nono ien able su aces.
We s a his sec ion summa izing he basic p ope ies o he locally Euclidean
su aces, ia hei plana ep esen a ion. A mo e comple e s udy o hem can be ound
in [15].
2.1. Locally Euclidean su aces. A 2-dimensional locally Euclidean su ace
is a su ace which is isome ic wi h he plane in sufficien ly small egions.
Amo ion in he plane is a map ha p ese es dis ances be ween poin s. The
g oup o mo ions in he plane is deno ed by Mo(R2) and consis s o ansla ions,
o a ions, eflec ions, and glide eflec ions.
Ag oupΓ⊆Mo(R2)issaid obeuni o mly discon inuous i he e exis s a
posi i e numbe dsuch ha i γis a mo ion in Γ and Pany poin in he plane being
γ(P)=P, hen he dis ance be ween Pand γ(P) is g ea e han o equal o d.
The e a e fi e diffe en ypes o uni o mly discon inuous g oups o mo ions o he
plane, up o isomo phisms: Types I, II.a, II.b, III.a, and III.b [15]. They can be
gene a ed as ollows:
•Type I is gene a ed by he iden i y mo ion.
•Type II.a is gene a ed by a ansla ion.
•Type II.b is gene a ed by a glide eflec ion.
•Type III.a is gene a ed by wo noncollinea ansla ion ec o s.
•Type III.b is gene a ed by a ansla ion and a glide eflec ion, he di ec ion
o he ansla ion ec o being o hogonal o he axis o he glide eflec ion.
Gi en a g oup Γ ⊆Mo(R2)andapoin Pin he plane, he o bi o P ia Γ,
deno ed Γ(P), is he se o he successi e images o Punde he ac ion o he elemen s
o Γ, ha is, Γ(P)={γ(P):γ∈Γ}. Fo any uni o mly discon inuous g oup o
mo ions Γ ⊆Mo(R2) he ollowing no ion o equi alence on poin s in he plane can
be defined: poin s Aand Ba e equi alen i hey belong o he same o bi ; namely,
he e exis s a mo ion γ∈Γ such ha γ(A)=B. The o bi s a e hen he equi alence
classes unde his ela ion. The se o all o bi s o R2unde he ac ion o Γ is w i en
as R2/Γ and is called he quo ien space. The dis ance be ween wo poin s (o bi s)
A=Γ(A)andB=Γ(B)inR2/Γ is defined o be he sho es o he dis ances |AB|,
whe e Aand Ba e poin s o he plane wi h Abelonging o Aand B o B.
E e y locally Euclidean su ace Σ co esponds o a uni o mly discon inuous g oup
Γ o mo ions o he plane so ha Σ can be ob ained om Γ as he quo ien space R2/Γ.
Hence he e a e exac ly fi e ypes o locally Euclidean su aces [15]: he plane (Type I),
he cylinde (Type II.a), he wis ed cylinde (Type II.b), he (fla ) o us (Type III.a),
and he Klein bo le (Type III.b). Al hough he e m la o us applies o su aces
gene a ed by any g oup o mo ions o Type III.b, we will ollow he con en ion ha
conside s he ansla ions o be o hogonal. I he ansla ions a e no o hogonal,
hen we call he su ace so ob ained a skew o us. As we will see in sec ion 4.2, his
dis inc ion is no i ial and has impo an consequences on he connec i i y o he
g aph o iangula ions.
Acco ding o he abo e defini ions and esul s, a poin ao he su ace defined by
a uni o mly discon inuous g oup Γ is specified by an o bi Ao Γ. Howe e , in o de
o speci y a, he e is no need o know all poin s o A; we need only know one poin A
o A, and hen all he o he s a e ob ained om Aby applying mo ions in he gi en
g oup Γ. The e o e, in o de o de e mine he se o all poin s o he su ace, we need
only speci y some egion o he plane, o example, a polygon, sa is ying he ollowing
p ope ies:
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
824 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
1. The egion con ains one poin om e e y se o equi alen poin s o he plane.
2. No in e io poin o he egion is equi alen o any o he poin o he egion;
ha is, equi alen poin s o he egion can lie only on he bounda y.
A egion in he plane sa is ying 1 and 2 is called a undamen al domain,and
he se o poin s on he su ace is ob ained om his egion by iden i ying o gluing
oge he equi alen poin s o i s bounda y. In gene al, we will use he undamen al
domains ha a e mo e common in he li e a u e, ha is, an infini e band o bo h he
cylinde and he wis ed cylinde and a ec angle on he o us and he Klein bo le.
In he skew o us i is also usual o conside as a undamen al domain a pa allelog am
whose sides a e pa allel o he di ec ion o he ansla ions.
In o de o fix he poin s in he examples gi en in sec ion 4, we will conside an
o hogonal e e ence sys em in hese su aces which will be cen e ed, o simplici y,
in he le mos side o he band o in he lowes le mos co ne o he ec angle (o
pa allelog am) conside ed as he undamen al domain. In he nono ien able case he
OX axis will be aken o coincide wi h one glide eflec ion axis o Γ. The essela ions
o he plane gene a ed by he p e ious undamen al domains o each su ace oge he
wi h he o bi o a polygon a e depic ed in Figu es 1 and 2.
(a) (b)
OY OY
OX OX
Fig. 1.The o bi o a polygon in (a) he cylinde and (b) he wis ed cylinde .
(a) (b)
OY OY
OX OX
Fig. 2.The o bi o a polygon in (a) he o us and (b) he Klein bo le.
2.2. T iangula ions o Euclidean polygons. Flips. AEuclidean polygon in
a locally Euclidean su ace is a egion homeomo phic o a closed disc and whose bound-
a y consis s o fini ely many geodesic a cs. A Euclidean polygon may be ep esen ed
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 825
as a simple plana polygon, al hough, depending on he elec ion o he undamen al
domain, i migh no be comple ely con ained in only one o hem.
F om now on, Euclidean polygons will be assumed o be al eady d awn in he
plane.
The segmen ( ha is, he minimum geodesic) be ween wo nonconsecu i e e ices
o a Euclidean polygon is called a diagonal o he polygon. The diagonal u is said
o be admissible i i is con ained inside he polygon (Figu e 3).
uu’
Fig. 3.Since he nea es copy o u om is u,uand canno be ma ched inside he polygon
and he diagonal u is no admissible.
A(me ical) iangula ion o a Euclidean polygon is a pa i ion o he polygon
in o iangula egions ( ha is, egions homeomo phic o a disc bounded by h ee
segmen s) by means o admissible diagonals wi h no in e sec ions excep o hei
ends. No e ha we o ce e e y ace o a iangula ion o be iangula ins ead o
conside ing a maximal se o segmen s since, despi e being equi alen defini ions in
he plane, his is no longe ue in o he su aces, as will be appa en in sec ion 4.2. In
he same way, we define iangula ions o poin se s as a maximal se o nonc ossing
segmen s such ha each bounded egion is iangula . On he con a y, wha happens
in Euclidean polygons, gi en a poin se he shape o he egion iangula ed, depends
on he posi ion o he poin s on he su ace, and i can be a Euclidean polygon, o a
s ip bounded by wo geodesics, o he whole su ace (see [3, 8]).
Le { i,
j,
k}and { i,
j,
l}be wo iangles in a iangula ion sha ing he
diagonal i j.By lipping i jwe mean he ope a ion o emo ing i jand eplacing
i by he o he diagonal k li i is admissible in he quad angle { i,
k,
j,
l}.The
g aph o iangula ions o a polygon o a poin se Pis he g aph TG(P) ha ing
as nodes he iangula ions o P, wi h adjacencies co esponding o diagonal flips
(Figu e 4).
3. G aph o iangula ions o a polygon on nonplana su aces. One
expec s ha me ical iangula ions depend s ongly on he me ic conside ed since
small changes in he me ic migh u n admissible diagonals in o nonadmissible ones
and flip pe o mance would be affec ed. In his sec ion, we define a me ic on he
sphe e ha p oduces polygons and poin se s wi h nonconnec ed g aphs o iangula-
ions. The same idea will be used o ex end his esul o a gene al closed connec ed
su ace.
On he sphe e, wi h i s na u al me ic, geodesics co espond o g ea ci cles and
he dis ance be ween wo poin s is he leng h o he sho es a c o he g ea ci cle
joining hem (Figu e 5), which is unique wi h he excep ion o an ipodal (o diame i-
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php

Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
826 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
Fig. 4.The g aph o iangula ions o a polygon in he plane.
Fig. 5.The dis ance be ween wo poin s in he sphe e is gi en by he sho es a c o he g ea
ci cle joining he poin s.
cally opposi e) poin s. A (Euclidean) polygon on he sphe e, as in a locally Euclidean
su ace, is a egion homeomo phic o a closed disc and whose bounda y consis s o
fini ely many geodesic a cs. T iangula ions, flips, and g aphs o iangula ions o
polygons on he sphe e a e also defined in he same way as hey we e in he p e ious
sec ion.
By using a gumen s simila o hose in [12], i can be es ablished ha he g aph
o iangula ions o any polygon on he sphe e is connec ed wi h his me ic. Bu i
is possible o sligh ly dis u b he me ic so ha his asse ion will no longe be ue.
Lemma 1. The e exis s a su ace Mhomeomo phic o he sphe e (in o he wo ds,
Mis a sphe e wi h a me ic o he han he Euclidean dis ance) such ha in M he e
exis s a Euclidean polygon wi h a nonconnec ed g aph o iangula ions and a poin
se also wi h a nonconnec ed g aph o iangula ions.
P oo . Conside a g ea ci cle C ha di ides he sphe e in o wo open hemisphe es
H1and H2.Le p1,p
2,...,p
6be a sequence o e ices uni o mly dis ibu ed on C
such ha he g ea ci cles joining (p1,p
4), (p2,p
5), and (p3,p
6) in e sec only in
wo an ipodal poin s nand sin H1and H2, espec i ely. We mo e he e ices
p1,p
2,...,p
6sligh ly owa d nun il he a c joining hem inside H1is sligh ly sho e
han he one ha c osses h ough H2.
Le L=p1,p
2,...,p
6be a closed polygonal chain s ic ly con ained in H1,
and le Pbe he polygon bounded by Lwhose in e io is he egion wi h a smalle
a ea o he wo in o which he su ace is di ided by he polygonal chain. Now, M
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 827
is ob ained om he sphe e by li ing up a small egion a ound nun il he dis ances
(conside ing he me ic inhe i om R3) be ween (p1,p
4), (p2,p
5), and (p3,p
6), a e
enla ged enough o ensu e ha he diagonals joining hem a e nonadmissible in P(so
hose admissible diagonals a e ex e io o P), bu wi hou changing he leng h o he
o he diagonals o P(Figu e 6(a)).
(
a
)
p3
p4
p1
p1
p5
p2
p6
p3
p4
p1
p5
p2
p6
(
b
)
Fig. 6.A hexagon wi h wo disjoin iangula ions in a “moun ainous” sphe e.
A e he li ing o he egion a ound n, he leng h o any geodesic inside H1on M
ei he is inc eased o emains he same as i s leng h be o e he li ing. Mo eo e , he
segmen s (sho es geodesic a cs) joining (p1,p
4), (p2,p
5), and (p3,p
6) a e he a cs o
he g ea ci cles ha join hose poin s in H2. The e o e, Padmi s only wo diffe en
iangula ions, shown in Figu e 6(b), which canno be ans o med in o each o he by
a sequence o flips, and hence, he g aph o iangula ions o Pis nonconnec ed.
Basically, he same example can be used o poin se s by adding a new e ex p7
on s. To comple e a iangula ion, join p7 o all he o he e ices o ob ain a se S.
By cons uc ion, i is no possible o pe o m flips in any o he quad ila e als ha ing
p7as a e ex ( he new diagonals a e ou side he quad ila e als). So, Shas he wo
diffe en iangula ions o he o iginal polygon P, and no flip is possible in any o
hose iangula ions.
Using he p e ious lemma, he same easoning can be ex ended o he emain-
ing closed connec ed su aces by using he ac ha e e y closed connec ed su ace
is opologically equi alen o a sphe e, o a connec ed sum o o i (handles), o a
connec ed sum o p ojec i e planes.
Theo em 1. Any closed connec ed su ace Sadmi s a me ic ha allows polygons
and poin se s whose g aphs o (me ical) iangula ions a e nonconnec ed.
P oo . Wecanmodi y hesu aceMdesc ibed in he p oo o Lemma 1 by
adding o i as many handles o p ojec i e planes as needed in o de o ob ain a
su ace homeomo phic o S.
By i ue o his ac , and mimicking he a gumen we ollowed on he sphe e, i
is possible o find a me ic on each closed and connec ed su ace ha allows polygons
and poin se s wi h nonconnec ed g aphs o iangula ions (see Figu e 7).
No e ha he easoning used in he p oo o Theo em 1 can be easily ex ended
o any kind o su ace.
4. Connec i i y o he g aph o iangula ions on locally Euclidean su -
aces. As has been said in he in oduc ion, some o he mos common and use ul
su aces a e he locally Euclidean su aces because o he ad an age o hei plana
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
828 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
Fig. 7.The cons uc ion o Figu e 6on he sphe e wi h wo handles.
ep esen a ions. I is in e es ing o emphasize he diffe en beha io ha hese su -
aces show when we s udy he g aph o iangula ions o a polygon: while he g aph
o iangula ions is connec ed bo h in he cylinde and in he fla o us, polygons wi h
nonconnec ed g aphs can easily be cons uc ed in he wo nono ien able su aces. The
beha io o he g aph o iangula ions in he o us is ema kable, since ha g aph is
connec ed o polygons wi h he me ic o he fla o us, bu his is no ue o he
skew o us. On he o he hand, he g aph o a poin se is nonconnec ed in gene al,
bu , as we shall see nex , we can desc ibe all he connec ed componen s in he case
o he cylinde .
4.1. The cylinde . Le a be he ec o ha gene a es he cylinde . Gi en
ha an o hogonal e e ence sys em is he OX axis pa allel o a, a geodesic a c is a
segmen i and only i i s e ical p ojec ion is smalle han |a|/2. In o de o add a
new diagonal o a iangula ion, a p ocedu e o de e mine i he geodesic a c joining
wo e ices i is a segmen is o check i i s e ical p ojec ion is con ained inside he
e ical p ojec ion o a p e iously exis ing diagonal (and, he e o e, a segmen ).
4.1.1. Polygons. I he plana copies o a polygon Pon he cylinde a e (each o
hem) s ic ly con ained in e ical bands o leng h |a|/2, hen any in e nal diagonal
is admissible and plana a gumen s can s aigh o wa dly be used o es ablish he
connec i i y o he g aph o iangula ions [8].
Howe e , al hough many diffe en p oo s a e known o plana polygons in he
plane, he au ho s a e no awa e o any p oo ha can be adap ed o he gene al case.
Ac ually, i is no e en ob ious ha in his gene al si ua ion a polygon can always be
iangula ed; al hough, in his case, essen ially he same ideas as in he plane p o ide
a p oo o his ac .
Lemma 2. Any Euclidean polygon o n≥4 e ices on he cylinde has an
admissible diagonal. Hence, any Euclidean polygon on he cylinde is iangulable.
P oo . This p oo is based on he p oo o Meis e ’s lemma [14], which es ablishes
he same esul o simple polygons in he plane.
Conside a Euclidean polygon Pal eady de eloped in he plane. Le be a con ex
e ex such ha he wo edges inciden on i go upwa d ( ecall ha a e ex is con ex
i i s in e io angle is less han π adians; o he wise, he e ex is e lex ). Le aand b
be he e ices adjacen o (Figu e 8).
I ab is an admissible diagonal (a segmen con ained in P), hen we ha e finished.
O he wise, ei he ab in e sec s ∂P o i is ex e io o P.
I ab in e sec s ∂P, he a gumen gi en in [14] can be mimicked: S a sweeping a
line om , keeping i pa allel o he line h ough ab, un il i eaches ano he e ex
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 829
a
b
a
b
Fig. 8.The segmen ma ching aand bmay o may no de e mine a bounded iangle.
x
a
b
Fig. 9. x is an inne diagonal o he polygon.
a
b
x
'
Fig. 10. is a diagonal o he polygon.
xo P(i mus exis since Phas a leas ou e ices). Then, x is an admissible
diagonal (Figu e 9).
I ab is ex e io o P, conside he e ical ay (hal -line) wi h as endpoin , and
le xbe he fi s poin o he bounda y o P ha i eaches. I xis a e ex, hen x
is an admissible diagonal. O he wise, o a e he ay ei he o he igh o o he le
un il i in e sec s ano he e ex o P(Figu e 10). The e ical p ojec ion o 
is con ained inside he e ical p ojec ion o he diagonal con aining x,so is an
admissible diagonal.
The connec i i y o he g aph o iangula ions o a Euclidean polygon on he
cylinde is es ablished by he nex heo em. As in he plane, h ee consecu i e e ices
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
836 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
Theo em 4. The g aph o iangula ions o a polygon on he la o us is ei he
emp y o connec ed.
P oo .Le T1and T2be wo iangula ions o a polygon Pon he fla o us. Le u
be an ex eme ea able e ex in P, which exis s by Lemma 4. By i ue o Lemma 5,
T1( esp., T2) can be ans o med by a sequence o flips in o ano he iangula ion T
1
( esp., T
2) ha ing an ea in u. The e o e, T
1and T
2a e connec ed by he induc i e
hypo hesis using flips.
Rega ding he connec i i y o he g aph o iangula ions o a poin se Sin he
fla o us he e a e h ee possible si ua ions:
1. I Sis inside a quad an , hen Sis in Euclidean posi ion, and i has a plana
beha io [3], so he g aph is connec ed.
2. I a plana copy o Sis inside a e ical ( esp., ho izon al) s ip o wid h |a|/2
( esp., |
b|/2), he si ua ion is equi alen o he cylinde . The g aph is connec ed i
and only i he bo de s o he iangula ed egion a e fixed (sec ion 4.1).
3. In he o he case he connec i i y o he g aph o iangula ions is s ill an
open p oblem. Ou conjec u e is ha his g aph is connec ed.
Ne e heless, as we poin ed ou in sec ion 3, he connec i i y o he g aph o
iangula ions is no p ese ed i he o us is gene a ed by wo nono hogonal ans-
la ions. In his way, conside he plana ep esen a ion o a skew o us gene a ed by
wo ansla ions wi h ec o s o ming an angle o a ccos 1
5. In o de o simpli y he
coo dina es o he e ices, we choose a ho izon al uni a y ec o and he o he one
wi h modulo 2√5
5, and hence he heigh o a undamen al egion is one uni . Using
he usual e e ence sys em, we can d aw a hexagon o e ices a(1
2+ε, 3
4), b(1 −ε, 3
4),
c(1 + ε
3,1
2), d(1 −ε, 1
4), e(1
2+ε, 1
4), and (1
2−ε
3,1
2), wi h ε<1
8. Since he diagonals
ad,be,andc a e no admissible, i is no possible o pe o m flips in ei he o he
wo iangula ions depic ed in Figu e 20.
ab
c
d
e
ba
b
c
de
b
ab
babb
d
eed
Fig. 20.The p e ious hexagon wi h all he possible segmen s be ween i s e ices.
And, as we ha e done in sec ion 3, new poin s can be added o he p e ious
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php

Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 837
cons uc ion o ob ain a poin se wi h a nonconnec ed g aph o iangula ions. We
include poin s g(0,3
4), h(1
4,3
5), i(1
4,2
5), and j(0,1
4), as is shown in Figu e 21. The
cen al hexagon (bold lines) s ill admi s only six diagonals, gi ing ise o only wo
diffe en iangula ions, and he segmen s o he bounda y o he hexagon canno be
flipped. So he g aph o iangula ions o he se has wo connec ed componen s.
ab
c
d
e
b
b
c
d
b
ab
babb
d
eed
g
h
i
j
g
j
a
e
h
i
g
j
Fig. 21.I is no possible o ca y one o he iangula ions o he cen al polygon in o he
o he by flips.
The e o e, he p e ious example shows (applying a sui able angle ans o ma ion
i necessa y) he ollowing esul .
Theo em 5. I is possible o ind a polygon and a poin se on a skew o us such
ha hei g aphs o (me ical) iangula ions a e nonconnec ed.
I is wo h poin ing ou ha he p e ious esul leads o ano he p oo o Theo-
em 1.
4.3. Nono ien able locally Euclidean su aces. I is easy o embed in he
wis ed cylinde and in he Klein bo le a polygon whose g aph o iangula ions is
nonconnec ed. We look o a si ua ion simila o he one used p e iously o he skew
o us (Figu e 20)—a hexagon o e ices (in clockwise o de ) a,b,..., such ha all
he diagonals a e admissible excep o he diagonals (a, d), (b, e), and (c, ). This
hexagon has only wo iangula ions, and i is no possible o pe o m a flip.
Conside he wis ed cylinde wi h he usual coo dina e sys em, and assume a
glide eflec ion wi h uni a y ec o . The hexagon o e ices a(1
4+ε, 1
4), b(3
4−ε, 1
4),
c(3
4+ε
3,0), d(3
4−ε, −1
4), e(3
4+ε, −1
4), and (1
4−ε
3,0), wi h ε< 1
16 , has a nonconnec ed
g aph o iangula ions (Figu e 22).
The same cons uc ion can be easily ob ained on he Klein bo le. A simila
s udy can be ex ended o he o he su aces ob ained as he quo ien o he plane o e
a g oup o mo ions (Euclidean 2-o bi olds) i he g oup con ains a glide eflec ion.
In pa icula , his hexagon can also be embedded in o he p ojec i e plane wi h he
quo ien me ic.
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
838 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
ab
c
d
e
ab
c
d
e
Fig. 22.The segmen s ad,be,andc a e ou side he polygon.
By adding only wo new poin s, as Figu e 23 shows, he p e ious example can
be ex ended o a poin se wi h a nonconnec ed g aph o iangula ions. Again,
as we saw in sec ion 4.2 o he skew o us, he cen al hexagon has wo possible
iangula ions and no flip is possible inside i . And, since he segmen s o he bounda y
o he hexagon canno be flipped, he wo iangula ions belong o diffe en connec ed
componen s.
ab
c
d
e
g
h
ab
c
d
e
g
h
ab
c
d
e
Fig. 23.The only flips allowed a e es ic ed o he shaded egions.
Sligh ly mo e complica ed is he example gi en o he Klein bo le (Figu e 24),
bu he easoning is he same; he segmen s ha o m he cen al hexagon canno be
flipped; hence he se has wo disjoin iangula ions.
5. Conclusions and open p oblems. In his pape we ha e s udied he con-
nec i i y o he g aph o iangula ions o polygons and poin se s on a su ace. We
ha e seen ha , in gene al, his g aph is nonconnec ed. Mo e p ecisely, we ha e p o en
ha any su ace admi s a me ic such ha he e exis a polygon and a poin se on
ha su ace (and wi h ha me ic) wi h a nonconnec ed g aph o iangula ions.
The e exis some ema kable excep ions. The fi s among hese, o cou se, a e he
plane and he sphe e, and hen polygons on he cylinde and he fla o us, hese
su aces being he only ones o which Lawson’s me hod [12] o ob ain an op imal
iangula ion could be applied. Ne e heless he p ac ical applica ions o his me hod
a e no clea since we ha e no ound easonable bounds o he diame e o he g aph
o iangula ions in hese su aces.
Some p oblems a e s ill unsol ed. The main ques ion ha emains a e Theo-
em 1 is whe he i is possible o define a me ic in a su ace o cing he g aph o
iangula ions o any polygon o be connec ed, as has been shown o he o us.
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
TRANSFORMING TRIANGULATIONS ON NONPLANAR SURFACES 839
a
b
c
d
e
g
hi
g
hi
dc
b
a
d
a
e
b
a
c
d
e
a
dc
a
b
d
e
ih
h
i
g
g
Fig. 24.I is no possible o ca y one o he iangula ions o he cen al polygon in o he
o he by flips.
And, conce ning he fla o us, he connec i i y o he g aph is no es ablished i
i is associa ed o iangula ions o poin se s ins ead o polygons.
REFERENCES
[1] D. A is and K. Fukuda,Re e se sea ch o enume a ion, Disc e e Appl. Ma h., 6 (1996), pp.
21–46.
[2] M. Be n and D. Epps ein,Mesh gene a ion and op imal iangula ion, in Compu ing in
Euclidean Geome y, D. Z. Du and F. K. Hwang, eds., Wo ld Scien ific, Ri e Edge, NJ,
1992, pp. 23–90.
[3] C. Co es, A. Ma quez, and J. Valenzuela,Euclidean posi ion in euclidean 2-o bi olds,
Compu . Geom., 27 (2004), pp. 27–41.
[4] M. P. do Ca mo,Diffe en ial Geome y o Cu es and Su aces, P en ice–Hall, Englewood
Cliffs, NJ, 1976.
[5] M. Noy, F. Hu ado, and J. U u ia,Flipping edges in iangula ions, Disc e e Compu .
Geom., 22 (1999), pp. 333–346.
[6] S. Fo une,Vo onoi diag ams and Delaunay iangula ions, in Compu ing in Euclidean Ge-
ome y, D. Z. Du and F. K. Hwang, eds., Wo ld Scien ific, Ri e Edge, NJ, 1992, pp.
193–234.
[7] C. D. Gela , S. Ki kpa ick, and M. P. Vecchi,Op imiza ion by simula ed annealing,
Science, 220 (1983), pp. 671–680.
[8] C. I. G ima and A. M´
a quez,Compu a ional Geome y on Su aces, Kluwe Academic Pub-
lishe s, Do d ech , The Ne he lands, 2001.
[9] C. I. G ima, A. M´
a quez, and L. O ega,Anew2d essella ion o angle p oblems: The
pola diag am, Compu . Geom., 34 (2006), pp. 58–74.
[10] F. Hu ado and M. Noy,G aph o iangula ions o a con ex polygon and ee o iangula-
ions, Compu . Geom., 13 (1999), pp. 179–188.
[11] P. J. M. Van Laa ho en and E. H. L. Aa s,Simula ed Annealing: Theo y and P ac ice,
Kluwe Academic Publishe s, Do d ech , The Ne he lands, 1987.
[12] C. L. Lawson,T ans o ming iangula ions, Disc e e Ma h., 3 (1972), pp. 365–372.
[13] M. Maz´
on and T. Recio,Vo onoi diag ams on o bi olds, Compu . Geom., 8 (1997), pp.
219–230.
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php
Copy igh © by SIAM. Unau ho ized ep oduc ion o his a icle is p ohibi ed.
840 CORT´
ES, GRIMA, HURTADO, M ´
ARQUEZ, SANTOS, VALENZUELA
[14] G. H. Meis e ,Polygons ha e ea s, Ame . Ma h. Mon hly, 82 (1975), pp. 648–651.
[15] V. V. Nikulin and I. R. Sha a e ich,Geome ies and G oups, Sp inge Se ies in So ie
Ma hema ics, Sp inge , Be lin, 1987.
[16] A. Okabe, B. Boo s, and K. Sugiha a,Spa ial Tessela ions. Concep s and Applica ions o
Vo onoi Diag ams, John Wiley & Sons, New Yo k, 1992.
[17] M. Pocchiola and G. Veg e ,Compu ing he isibili y g aph ia pseudo- iangula ions,in
P oceedings o he 11 h Annual ACM Symposium on Compu a ional Geome y, ACM,
New Yo k, 1996, pp. 248–257.
[18] F. San os,Geome ic bis ella flips. The se ing, he con ex and a cons uc ion,inIn e na-
ional Cong ess o Ma hema icians, Vol. III, M. Sanz-Sol´e, J. So ia, J. L. Va ona, and J.
Ve de a, eds., Eu opean Ma hema ical Socie y, Helsinki, Finland, 2006, pp. 931–962.
[19] D. D. Slea o , R. E. Ta jan, and W. P. Thu s on,Ro a ions dis ance, iangula ions and
hype bolic geome y, J. Ame . Ma h. Soc., 1 (1988), pp. 647–682.
Downloaded 01/25/16 o 150.214.182.82. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php