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).