A completion of hypotheses method for 3D-geometry. 3D-extensions of Ceva and Menelaus theorems

A Comple ion o Hyp o heses Me ho d o 3D-Geome y. 3D-Ex ensions o Ce a and Menelaus Theo ems 1 E. Roanes-Maas a , E. Roanes-Lozano  ; a a Dep . Algeb a, Uni e sidad Complu ense de Mad id, Ediio La Almudena", / Re o Royo Vil lano a s/n, 28040-Mad id, Spain Abs a A me ho d ha au oma es hypo heses omple ion in 3D-Geome y is p esen ed. I onsis s o h ee p o esses: dening he geome i ob je s in he ongu a ion; de e mining he hyp o hesis ondi ions o he ongu a ion ( h ough a poin -on-ob je dela a ion me hod); and applying an algeb ai au oma i heo em p o ing me ho d o ob ain and p o e he suÆieny o omplemen a y hyp o hesis ondi ions. To a oid as muh as possible he app ea ane o a ional exp essions, p o je i e o o dina es a e used (al hough aÆne and Eulidean p oblems an also b e ea ed). A Maple implemen a ion o he me ho d has been used o ex end o 3D lassi 2D geome i heo ems like Ce a's and Menelaus'. Key wo ds: 3D-Geome y, Simb oly Compu a ion, Au oma i Theo em P o ing 1. B ie Des ip ion o he Me ho d Hyp o heses omple ion was al eady ea ed by Reio and Velez [6℄. The me ho d p esen ed in his pap e au oma es hypo heses omple ion in 3D- Geome y. Le us gi e a b ie des ip ion o i s h ee p o esses. 1.1. Dening he Geome i Obje s in he Congu a ion Among he geome i ob je s in a ongu a ion, some an b e dened di e ly and o he s a e de- e mined h ough geome i op e a ions (see Table 1). O he usual geome i ob je s inluded in he pakage (segmen , midp oin , sphe e, quad i,...) a e omi ed o he sake o spae. The desi ed ongu a ion an be ons u ed h ough he adequa e ona ena ion o hese el- emen a y ommands. No e ha in his Geome-  Co esp onding au ho Email add esses: oanesma .um.es (E. Roanes- Maas), e oanesma .um.es (E. Roanes-Lozano). 1 Pa ially supp o ed by he esea h p o je TIC-2000- 1368-C03-03 (MCyT, Spain). y no only he ule-and-ompass global ly on- s u ible ob je s an b e ea ed: hose geome - i ob je s suh ha any o hei p oin s an b e ons u ed wi h ule-and-ompass, an b e ea ed o o. P o je i e o o dina es a e used. Command in Coo allows o subs i u e o o dina es whe e a ional exp essions appea by he o esp onding in ege qua e nions. 1.2. De e mining he hypo hesis ondi ions o he ongu a ion Hyp o hesis ondi ions a e dela ed as membe - ship ela ions b e ween p oin s and highe dimension geome i ob je s. To dela e P = [ p 0 ; p 1 ; p 2 ; p 3 ℄ as a p oin on he ob je  (b eing he equa ions o  :  i ( x 0 ; x 1 ; x 2 ; x 3 ) = 0 ; i = 1 ; :::; n ) is equi - alen o imp ose ha he hypo hesis ondi ions  i ( P 0 ; P 1 ; P 2 ; P 3 ) = 0 ; i = 1 ; :::; n a e e ied. Command poin OnObje akes a e o adding hese p olynomials o a e ain lis , deno ed LRE L , whe e he hypo hesis polynomials a e s o ed, and o add he o esp onding a iables o he lis V AR . 20 h EWCG Se ille, Spain (2004) 20 h Eu op ean Wo kshop on Compu a ional Geome y Ob je Inpu Command Ou pu ini ial p oin ou p o je i e poin lis o 4 ( ee p oin ) o o dina es pa ame e s plane h ee non-ollinea plane equa ion o p oin s he plane line wo die en line lis o equa ions p oin s o he line p oin on line AB wo p oin s ( A; B ) a eOnLine lis o o o ds. ( ! P B =  ! P A ) and a eal numb e o p oin P plane/line pa allel one linea ob je pa allel equa ion(s) o o a gi en plane/line and one p oin he plane/line plane/line p e p endiula one linea ob je pe pendiula equa ion(s) o o a gi en line/plane and one p oin he plane/line in e se ion o wo wo al eady in e se ion o o ds. o p oin (s) ob je s (no dened ob je s o equa ion(s) o neessa ily linea ) linea ob je s o edued lis o eqs. (in GB sense) Table 1 Geome i ob je s' deni ion 1.3. Ob aining and P o ing he SuÆieny o Complemen a y Hypo hesis Condi ions In mos ongu a ion geome i p oblems, he hesis is (o an b e edued o) a P 2  memb e - ship ondi ion (whe e P is a poin and  is a geo- me i ob je ) o o a geome i ela ion among ge- ome i ob je s in he ongu a ion. In b o h ases he hesis polynomial admi s a  ( P ) o m. In ase lis LRE L is emp y, o hek ha he hesis holds is equi alen o hek ha  anishes in P (i.e., ha  ( P ) = 0). Command isPlaed applied o he pai ( P ;  ) akes a e o p e o ming all he o esp onding ompu a ions. In ase lis LRE L is no emp y, o hek ha he hesis holds i is suÆien o hek ha  an b e exp essed as an algeb ai linea ombina ion o he p olynomials in lis LRE L , wha an b e e - e i ely ompu ed using Wu's ehniques. A b ie des ip ion o hese au oma i p o ing ehniques an b e ound in [1℄, meanwhile a de ailed des ip- ion an be ound, e.g., in [2,9℄. These ehniques we e adap ed o hyp o heses omple ion in [5℄ and o geome i loi de e mining in [7℄. The ehnique des ib ed in his pap e is essen ially ha o [7℄, bu has b een adap ed o he way hyp o hesis and hesis ondi ions a e usually dela ed. This p o ess basially onsis s o wo s eps: { o iangula ize sys em LRE L w. . . he a i- ables in lis V AR , o ob ain sys em T RI P { o ompu e, s a ing wi h  ( P ), he suessi e pseudo- emainde s o di iding by he p olynomi- als in T RI P w. . . he a iables in V AR , un il he las pseudo- emainde (p olynomial ! ) is ob- ained. Tha ! = 0 is a neessa y ondi ion o he he- sis o hold. Command newHypo o ou pakage, applied o ( P ;  ), au oma ially ompu es ! . Bu we would s ill ha e o hek ha ! = 0 is a suÆien ondi ion o he hesis  ( P ) = 0 o hold. I a pa ame iza ion o ! = 0 an be ob ained, hen we subs i u e in  ( x 0 ; x 1 ; x 2 ; x 3 ) he x i by hei o esp onding pa ame i exp essions. I he esul ing p olynomial anishes, hen ondi ion ! = 0 is also suÆien . Command isPlaed an ake a e o hese ompu a ions. I a pa ame iza ion o ! = 0 an' be ob ained, hen ! is b e added o lis LRE L , and he new a i- able app ea ing in ! bu no in lis V AR , is added o lis V AR . The same p o ess an b e applied now, Ma h 25-26, 2004 Se ille (Spain) and, i he las pseudo- emainde is 0, hen ondi- ion ! = 0 is also suÆien . Command au P o e an ake a e o hese ompu a ions. 2. 3D-Ex ension o Ce a and Menelaus Theo ems An applia ion o he au oma i heo em p o - ing me ho d des ib ed ab o e is inluded as illus a- ion a e wa ds. The goal is o de e mine ondi- ions ha make ou p oin s, lying on onseu i e edge-lines o a e ahed on, oplana y (see Figu e 1). This p oblem was een ly sol ed using syn- he i ehniques by H. Da is [3℄. Fig. 1. Ex ending o 3D Ce a and Menelaus heo ems We an assume ha he e ies a e A (1 ; 0 ; 0 ; 0), B (1 ; 1 ; 0 ; 0), C (1 ;  1 ;  2 ; 0), D (1 ; Æ 1 ; Æ 2 ; Æ 3 ) wi h- ou any lak o gene ali y ( hese p oin s an b e dened using ommand poin ). Gi en m; n; p; q 2 R [ 1g , le M ; N ; P ; Q b e he p oin s lying on he edge-lines AB ; B C; C D ; D A ( esp e i ely), and sa is ying ! M B = m  ! M A ; ! N C = n  ! N B ! P D = p  ! P C ; ! QA = q  ! QD ( hey an b e dened using ommand a eOnLine ). Then plane MNP an be dened (using ommand plane ). As de ailed ab o e, applying ommand newHypo o he pai ( Q; M N P ), a neessa y ondi ion o Q o lie on plane MNP (i.e., o M ; N ; P ; Q o b e oplana y):   2  Æ 3  (  1 + m  n  p  q ) = 0, is ob ained. As A; B ; C; D a e non-oplana y p oin s, and onsequen ly,  2 6 = 0 6 = Æ 3 , wha implies: m  n  p  q = 1. To e i y ha is a suÆien ondi ion, Q is pa iula ized o q = 1 = ( m  n  p ), and applying ommand isPlaed o he pai ( Q; M N P ), 0 is ob ained, wha on ms ha Q b elongs o plane MNP . This leads o he ollowing: Theo em 1 Poin s M ; N ; P ; Q , lying on he o i- en ed onseu i e edge-lines AB ; B C ; C D ; D A o e ahed on AB C D ( espe i ely), a e oplana y, i and only i : ( M B =M A )  ( N C =N B )  ( P D =P C )  ( QA=QD ) = 1 Obse e ha he p oin s M ; N ; P ; Q do lie on he onseu i e o ien ed edge-lines AB ; B C ; C D ; D A , bu hey an lie ou side he edge-segmen s, and he e o e his esul do esn' only gene alizes Ce a heo em, bu also Menelaus heo em. 3. Compa ison wi h O he Me ho ds As he au oma i heo em p o ing ehnique used in his wo k is based on Wu's algo i hm, i is o a lowe ompu a ional omplexi y han hose ehniques based on he use o G oebne bases. Compa ing his me ho d wi h o he s based on Wu's ehniques, he main die ene is he way he geome i ob je s o he ongu a ion a e de- ned and he way he hyp o heses ondi ions a e dela ed. In he me hod p esen ed he e he geo- me i ob je s and he hypo heses ondi ions a e ob ained in a na u al way, ollowing he geome - i algo i hm ha gene a es he ongu a ion, in- s ead o ansla ing in o algeb ai exp essions he geome i ela ions ha de e mine hem (wha is usually he ase). Tha happens, o ins ane, in Simson-S eine - Guzman heo em 3D-ex ension [4℄. The goal is o de e mine he ondi ions so ha he p o je ions (in p exed di e ions) o a p oin on he aes o a e ahed on a e oplana y. This p oblem was de- elop ed in [7℄, ansla ing in o algeb ai exp es- sions he geome i ela ions. Now i has b een de- elop ed using he me hod de ailed in se ion 1, in a mo e om o able and as e way. 20 h Eu op ean Wo kshop on Compu a ional Geome y O he ad an age o he me ho d p op osed in Se- ion 1 is he simple way in whih pa ame e s and a iables a e dis inguished (wha is no s aigh - o wa d in o he app oahes). Wi h his me ho d he pa ame e s a e he non-nume i o o dina es o he ini ial p oin s ( ha a e p ese ed along all sub- sequen alula ions), meanwhile he a iables a e he o o dina es o he p oin -on-ob je ob je s de- ned using poin OnObje ommand. Ano he ad an age o he me ho d p op osed in Se ion 1 is he p ossibili y o de elop he geome - i algo i hm o he ongu a ion using a Dynami Geome y Sys em, and o ansla e i o a Com- pu e Algeb a Sys em syn ax (in e p e ing i using he pakage onside ed he e), as al eady done in 2D [8℄. We plan o implemen i in he nea u u e. 4. Conlusions The hypo heses omple ion in 3D-Geome y me ho d des ib ed is on enien and eÆien . I allows he use o ob ain au oma ially he equa- ions in he ongu a ion, he hyp o hesis ondi- ions ob ained di e ly in he ongu a ion and he omplemen a y hyp o hesis ondi ions ha ha e o b e added o he hesis ondi ion o hold. Re e enes [1℄ D. Cox, J. Li le and D. O'Shea, Ideals, Va ie ies, and Algo i hms (Sp inge , New Yo k, 1991). [2℄ S. C. Chou, Mehanial Geome y Theo em P o ing (Reidel, Do d eh , 1988). [3℄ H. Da is, Menelaus and Ce a Theo ems and i s many applia ions, h p://hamil onious. i uala e.neg / essays/o he/nalpape 4.h m [4℄ M. de Guzman, An Ex ension o he Wallae- Simson Theo em: P o je ing in A bi a y Di e ions, Ma hema ial Mon hly 106/6 (1999) 574{580. [5℄ D. Kapu and J.L. Mundy, Wu's me ho d and i s applia ion o p e sp e i e iewing, in: D. Kapu , J.L. Mundy, eds., Geome i Reasoning (MIT P ess, Camb idge MA, 1989) 15{36. [6℄ T. Reio and M. P. Velez, Au oma i Diso e y o Theo ems in Elemen a y Geome y, Jou nal o Au oma ed Reasoning 23 (1999) 63{82. [7℄ E. Roanes-Maas and E. Roanes-Lozano, Au oma i de e mina ion o geome i lo i, in: J. A. Camb ell and E. Roanes-Lozano, eds., A iial In el ligene and Symboli Compu a ion . (Sp inge 's Le u e No es in A iial In elligenge no. 1930, Be lin, 2000) 157{173. [8℄ E. Roanes-Lozano, E. Roanes-Maas and M. Villa , A B idge Be ween Dynami Geome y and Compu e Algeb a, Ma hema ial and Compu e Model ling 37/9- 10 (2003) 1005{1028. [9℄ W. T. Wu, Mehanial Theo em P o ing in Geome ies (Sp inge -Ve lag's Tex and Monog aphs in Symb oli Compu a ion, Wien, 1994).