Verification of partitions of 2d and 3d objects

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.