Ve i ica ion o Pa i ions o 2d and 3d Objec s
Leonidas Palios
Depa men o Compu e Science, Uni e si y o Ioannina, 45110 Ioannina, G eece
Abs ac
We conside he p oblems o deciding whe he a gi en collec ion o polygons (polyhed a esp.) o ms (i) a pa i ion
o (ii) a cell complex decomposi ion o a gi en polygon (polyhed on esp.). We desc ibe simple O(nlog n)- ime
and O(n)-space algo i hms o hese p oblems, whe e nis he o al desc ip ion size o he inpu . I , in he inpu ,
e ices a e e e enced by means o indices o an a ay o dis inc e ices, hen ou cell complex decomposi ion
e i ica ion algo i hms un in O(n) ime.
1. In oduc ion
In ecen yea s, he e has been g owing in e es
in algo i hms ha enable us o check he ou pu
o a p og am. This issue has been conside ed om
di e en iewpoin s, and he esea ch yielded e-
sul s anging om cha ac e iza ions o p oblems
ha a e checkable [2] o special-pu pose checke s.
In pa icula , in compu a ional geome y, his is-
sue p o es o be c ucial as he newe and mo e e -
icien algo i hms a e mo e and mo e complica ed.
Usually, he au ho s o an algo i hm o compu ing
some geome ic objec desc ibe p ope ies o he
objec which can be used o e i y he co ec ness
o he compu a ion (see e.g. [1] and [4] o 2d and
3d iangula ions o poin se s). O en, howe e ,
mo e machine y is needed.
The i s e i ica ion algo i hms (“checke s”)
we e p o ided by Mehlho n e al. who de ined he
p ope ies ha a checke should ha e (co ec -
ness, simplici y, e iciency) and desc ibed check-
e s o con ex polyhed a and con ex hulls [5];
hey ha e also s udied checke s o apezoidal
decomposi ions, plana poin loca ion s uc u es
o apezoidal decomposi ions, and Vo onoi and
Delaunay diag ams. De ille s e al. ex ended he
no ion o checke s and p o ided checke s o con-
ex poly opes in wo and highe dimensions, and
o a ious ypes o plana subdi isions [3]. Thei
algo i hms un in linea ime, assuming ha he
inpu is a 2d o a 3d o de ed geome ic g aph.
Email add ess: [email protected] (Leonidas Palios).
In his pape , we p esen simple and e icien
e i ica ion algo i hms o pa i ions and cell
complex decomposi ions o simple polygons and
polyhed a. The algo i hms ely on app op ia ely
ma ching he edges o he 2d decomposi ions and
he ace s o he 3d decomposi ions, and un in
O(nlog n) ime using O(n) space, whe e nis he
o al size o he inpu . I , in he inpu , e ices a e
e e enced by means o indices o an a ay o dis-
inc e ices, hen ou cell complex decomposi ion
e i ica ion algo i hms un in op imal O(n) ime.
No e: In he ollowing, a polygon o a polyhed on
is unde s ood o be a simple one.
2. The Two-dimensional Case
We assume ha each polygon in he inpu is
desc ibed by he sequence o i s e ices along i s
bounda y, whe e each e ex is gi en by i s coo -
dina es.
2.1. Ve i ica ion o a pa i ion o a polygon
Lemma 1 Le Pand Cbe a polygon and a collec-
ion o polygons espec i ely. Addi ionally, le EI=
{e−∂P |eis an edge o a polygon in C} and EB=
{e∩∂P |eis an edge o a polygon in C}. Then, he
collec ion C o ms a pa i ion o Pi and only i
(i) he se EIo (pa s o ) edges o he polygons in
Ccan be pa i ioned in o se s Sand S′such ha
•Ss∈Sclosu e(s) = Ss∈S′closu e(s),
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
• he closu es o he segmen s in Sand S′de ine
a pa i ion o Ss∈Sclosu e(s), and
• o each (pa o ) edge ein S( esp. S′), i S′[e]
( esp. S[e]) is he se o segmen s o S′( esp. S)
ha a e collinea wi h and in e sec e, hen,
locally a ound e, he in e io o he polygon in
Cwi h edge eand he in e io s o he polygons
in Cwhose edges con ibu ed he elemen s o
S′[e]( esp. S[e]) lie on opposi e sides o he
line suppo ing e;
(ii) he closu es o he segmen s in EB o m a pa i-
ion o he bounda y ∂P o P, and o each (pa
o ) edge ein EB, locally a ound e, he in e io o
he polygon in Cwi h eas an edge and he in e-
io o Plie on he same side wi h espec o he
line suppo ing e.
The pa i ion e i ica ion algo i hm applies
Lemma 1. I uses an (ini ially emp y) a ay A
o size equal o he o al numbe o edges o he
polygons in Cand o he polygon P.
2d Pa i ion Ve i ica ion Algo i hm
1. O ien he bounda y o polygon Pand he
bounda ies o he polygons in Cin a compa -
ible ashion (e.g., he bounda y is a e sed
in a ccw ashion).
2. Fo each polygon Qin Cdo
o each edge −→
u o Qdo
i uis lex-smalle han
hen add he en y (u, , +1) in A;
else add he en y ( , u, −1) in A;
3. Fo each edge −→
u o Pdo
i uis lex-smalle han
hen add he en y (u, , −1) in A;
else add he en y ( , u, +1) in A;
4. So he en ies (ui, i,±1) o he a ay Aby
slope o he line ui iand, in case o ies, lex-
icog aphically aking in o accoun he coo -
dina es o he e ices uiand i.
5. Fo each slope sepa a ely, a e se he ela ed
en ies o A e i ying ha hose wi h “+1”
and hose wi h “−1” pa i ion he same se
o segmen s. I his e mina es success ully,
hen he collec ion Co polygons de ines a
pa i ion o he polygon P, o he wise i does
no .
Time complexi y. S eps 1, 2, and 3 can be com-
ple ed in ime linea in he o al desc ip ion size n
o he inpu , while S ep 4 akes O(nlog n) ime.
S ep 5 akes O(n) ime: o each slope, he so -
ing o he en ies implies ha each new en y wi h
“+1” ei he is he ex ension o he la es en y wi h
“+1” o s a s a new segmen in he union o he
“+1”-en ies (i no , Cdoes no o m a pa i ion o
P), and simila ly o he “−1”-en ies. The algo-
i hm uses O(n) space.
2.2. Ve i ica ion o a cell complex decomposi ion
o a polygon
Lemma 2 Le Pand Cbe a polygon and a collec-
ion o polygons espec i ely. Then, he collec ion C
o ms a cell complex decomposi ion o Pi and only
i he se o edges o he polygons in Ccan be pa i-
ioned in o wo se s EIand EBsuch ha
(i) o each edge ein EI he e exis s exac ly one
o he edge, say d, in EIsuch ha e=dand,
locally a ound e, he in e io s o he polygons in
Cwi h edges eand dlie on opposi e sides o he
line suppo ing e;
(ii) he edges in EB o m a pa i ion o he bound-
a y ∂P o Pand o each edge ein EB, locally
a ound e, he in e io o he polygon in Cwi h
edge eand he in e io o Plie on he same side
wi h espec o he line suppo ing e.
The cell complex e i ica ion algo i hm applies
Lemma 2; i oo uses an (ini ially emp y) a ay A
o size equal o he o al numbe o edges o he
polygons in C.
2d Cell Complex Ve i ica ion Algo i hm
1. Collec all he e ices and assign o each one
o hem a dis inc posi i e in ege id( ).
2. O ien he bounda y o polygon Pand he
bounda ies o he polygons in Cin a compa-
ible ashion.
3. Fo each polygon Qin Cdo
o each edge −→
u o Qdo
i uis lex-smalle han
hen add (id(u), id( ),+1) in A;
else add (id( ), id(u),−1) in A;
4. So he a ay Alexicog aphically.
5. T a e se he so ed a ay Adele ing ma ch-
ing en ies (i.e., (k, k′,−1) and (k, k′,+1)),
which now appea nex o each o he .
6. Collec he unma ched en ies and by ap-
plying a dep h- i s a e sal cons uc he
g aph ha hese en ies o m. I his g aph
is a closed pa h iden ical o he bounda y o
he polygon P, hen he collec ion Co poly-
Ma ch 25-26, 2004 Se ille (Spain)
gons de ines a cell complex decomposi ion o
P, o he wise i does no .
Time complexi y. I nis he o al desc ip ion size
o he inpu , S ep 1 can be execu ed in O(nlog n)
ime by means o a balanced bina y sea ch ee
o de e mine iden ical e ices. S eps 2 and 3 ake
O(n) ime; so does S ep 4 (by using adix so ing),
and S eps 5 and 6. Thus, he algo i hm akes a
o al o O(nlog n) ime. The space equi ed by he
algo i hm is O(n).
Obse e ha all he s eps o he abo e algo i hm
bu S ep 1 ake O(n) ime. Mo eo e , i he inpu
consis s o he lis Vo dis inc e ices o he poly-
gon Pand o he polygons in he collec ion C, ol-
lowed by he e ices o each polygon, whe e each
e ex is e e enced by i s index o he lis V, hen
we do no need o execu e S ep 1. Such a ep esen-
a ion is commonly used, and is easily p oduced by
pa i ioning p og ams. Then, i can be de e mined
whe he he collec ion C o ms a cell complex de-
composi ion o Pin O(n) ime using O(n) space.
3. The Th ee-dimensional Case
We assume ha each polyhed on in he inpu is
desc ibed by a lis o i s ace s, each ep esen ed
by he sequence o i s e ices along i s bounda y,
whe e each e ex is gi en by i s coo dina es.
Ou e i ica ion algo i hms ely on wo lemma a
simila o Lemma 1 and Lemma 2.
3.1. Ve i ica ion o a pa i ion o a polyhed on
Lemma 3 Le Pand Cbe a polyhed on and a col-
lec ion o polyhed a espec i ely. Addi ionally, le
FI={ −∂P | is a ace o a polyhed on in C}
and FB={ ∩∂P | is a ace o a polyhed on in
C}. Then, he collec ion C o ms a pa i ion o Pi
and only i
(i) he se FIo (pa s o ) ace s o he polyhed a in
Ccan be pa i ioned in o wo se s Sand S′such
ha he closu es o he polygons in each o hese
se s de ines a pa i ion o Ss∈Sclosu e(s), and
o each (pa o ) ace in S(S′ esp.), he
in e io o he polyhed on o Cwi h ace and
he in e io s o he polyhed a o Cwi h ace s he
polygons o S′(S esp.) which in e sec wi h lie
(locally a ound ) on opposi e sides o he plane
suppo ing ;
(ii) he closu es o he polygons in FB o m a pa i-
ion o he bounda y ∂P o P, and o each (pa
o ) ace in FB, locally a ound , he in e io
o he polyhed on o Cwi h ace and he in e-
io o Plie on he same side wi h espec o he
plane suppo ing .
In ligh o Lemma 3, we ha e:
3d Pa i ion Ve i ica ion Algo i hm
1. O ien he ace s o he polyhed on Pand o
he polyhed a in Cin a compa ible ashion
(i.e., in coun e clockwise o de as seen om
ou side he polyhed on).
2. Fo each polyhed on Qin Cdo
o each ace o Qdo
u← he lex-smalles e ex o ;
i ’s bounda y o ms a le u n a u
hen add he en y ( , +1) in A;
else add he en y ( , −1) in A;
3. Fo each ace o Pdo
u← he lex-smalles e ex o ;
i ’s bounda y o ms a le u n a u
hen add he en y ( , −1) in A;
else add he en y ( , +1) in A;
4. So he en ies ( i,±1) o he a ay Aby
slope o he plane suppo ing iand, in case
o ies, lexicog aphically on he second ield
o he en y.
5. Fo each slope sepa a ely, e i y ha he e-
la ed ace eco ds wi h “+1” and hose wi h
“−1” pa i ion he same polygonal egions.
I his ma ching e mina es success ully, hen
he collec ion Cde ines a pa i ion o he
polyhed on P, o he wise i does no .
Time complexi y. S eps 1, 2, and 3 can be com-
ple ed in ime linea in he o al desc ip ion size n
o he inpu . S ep 4 akes O(nlog n) ime. S ep 5
can also be comple ed in O(nlog n) ime: o each
di e en plane slope, collec he en ies wi h “+1”
as second ield, and apply on he associa ed ace s
S eps 2 and 4 o he 2d pa i ion e i ica ion algo-
i hm (see Sec ion 2.1); S ep 5 o ha algo i hm
is applied nex , excep ha he di e ence o he
union o he “+1” and he “−1” en ies is com-
pu ed and used o o m a g aph; he same p o-
cedu e is applied o he en ies o he a ay A
wi h “−1” as second ield; inally, he wo esul ing
g aphs a e checked o see whe he hey a e iden i-
20 h Eu opean Wo kshop on Compu a ional Geome y
cal. Thus, he algo i hm akes a o al o O(nlog n)
ime. The algo i hm uses O(n) space.
3.2. Ve i ica ion o a cell complex decomposi ion
o a polyhed on
Lemma 4 Le Pand Cbe a polyhed on and a col-
lec ion o polyhed a espec i ely. Then, he collec-
ion C o ms a cell complex decomposi ion o Pi
and only i he se o ace s o he polyhed a in Ccan
be pa i ioned in o wo se s FIand FBsuch ha
(i) o each ace in FI he e exis s exac ly one
o he ace , say ′, in FIsuch ha = ′and,
locally a ound , he in e io s o he polyhed a in
Cwi h edges and ′lie on opposi e sides o he
plane suppo ing ;
(ii) he edges in FB o m a pa i ion o he bound-
a y ∂P o Pand o each ace in FB, locally
a ound , he in e io o he polyhed on o Cwi h
ace and he in e io o Plie on he same side
wi h espec o he plane suppo ing .
The cell complex e i ica ion algo i hm applies
Lemma 4. I uses wo auxilia y a ays Aand B,
which a e ini ially emp y; i wo ks as ollows:
3d Cell Complex Ve i ica ion Algo i hm
1. Collec all he e ices and assign o each one
o hem a dis inc posi i e in ege id( ).
2. O ien he ace s o he polyhed on Pand o
he polyhed a in Cin a compa ible ashion.
3. Fo each polyhed on Qin Cdo
o each ace o Qdo
a← he lex-smalles e ex o ;
b← he lex-la ges e ex o ;
c← ’s e ex a hes away om he
line ab (and lex-smalles , i ies);
i ’s bounda y is di ec ed a c b
hen add ((id(a), id(b), id(c)),+1) in A;
else add ((id(a), id(b), id(c)),−1) in A;
4. So he a ay Alexicog aphically.
5. T a e se he so ed a ay A, e i y ha
ma ched en ies (which now appea nex o
each o he ) co espond o ma ching ace s
and dele e hem.
6. Fo each ace whose en y in Ahas no
been ma ched do
o each edge −→
u o do
i uis lex-smalle han
hen add (id(u), id( ),+1, ) in B;
else add (id( ), id(u),−1, ) in B;
7. So he a ay Blexicog aphically.
8. I he en ies in Bdo no appea in ma ching
pai s (i.e., (k, k′,−1, ) and (k, k′,+1, ′)),
hen he collec ion Co polyhed a does no
de ine a cell complex decomposi ion o he
gi en polyhed on P.
9. Fo each ma ching pai (id(u), id( ),−1, )
and (id(u), id( ),+1, ′) in Bdo
i he wo ace s , ′a e no coplana
hen make uand adjacen ;
10. Apply a dep h- i s a e sal and check ha
he g aph o med ma ches he edge skele on
o he polyhed on P. I i does, hen he col-
lec ion Co polyhed a de ines a cell complex
decomposi ion o P, o he wise i does no .
Time complexi y. S ep 1 akes O(nlog n) ime,
as desc ibed in Sec ion 2.2. S eps 2, 3, 5, and 6
ake O(n) ime. S eps 4 and 7 can be comple ed in
linea ime as well by using adix so ing. Finally,
S eps 8, 9, and 10 also ake linea ime. Thus, he
algo i hm equi es a o al o O(nlog n) ime. The
space equi ed by he algo i hm is O(n).
Simila ly o he wo-dimensional case, i he
polyhed on Pand he polyhed a in he collec ion C
a e ep esen ed by a lis o ace s, each desc ibed
by a sequence o indices o an a ay o dis inc
e ices which indica es he o de o he e ices
a ound he bounda y o he ace , hen i can be
de e mined whe he he collec ion C o ms a cell
complex decomposi ion o Pin ime and space
linea in he o al desc ip ion size o Pand C.
Re e ences
[1] D. A is and H. El Gindy, T iangula ing poin se s in
space, Disc e e and Compu a ional Geome y 2, 99–
111, 1987.
[2] M. Blum and S. Kannan, Designing p og ams ha
check hei wo k, Jou nal ACM 42(1), 269–291, 1995.
[3] O. De ille s, G. Lio a, F.P. P epa a a, and
R. Tamassia, Checking he con exi y o poly opes
and he plana i y o subdi isions, Compu a ional
Geome y: Theo y and Applica ions 11(3-4), 187–208,
1998.
[4] H. Edelsb unne , F. P epa a a, and D. Wes ,
Te ahed alizing poin se s in 3 dimensions, Jou nal
o Symbolic Compu a ion,10, 335–347, 1990.
[5] K. Mehlho n, S. N¨ahe , T. Schilz, S. Schi a, M. Seel,
R. Seidel, and C. Uh ig, Checking geome ic p og ams
o Ve i ica ion o geome ic s uc u es, P oc. 12 h
Symp. on Compu a ional Geome y, 159–165, 1996.