Re isi ing Va iable Radius Ci cles in Cons uc i e
Geome ic Cons ain Sol ing
Ching-Shoei Chiang
Depa men o Compu e and In o ma ion Science
Soochow Uni e si y
Taiwan, R.O.C.
Robe Joan-A inyo
Depa amen de Llengua ges i Sis emes In o m`a ics
Uni e si a Poli `ecnica de Ca alunya
Ba celona, Ca alonia, Spain
[email p o ec ed], [email p o ec ed]
Ma ch 13, 2002
Abs ac
Va iable- adius ci cles a e common cons uc s in plana cons ain
sol ing and a e usually no handled ully by algeb aic cons ain sol e s.
We gi e a comple e ea men o a iable- adius ci cles when such a
ci cle mus be de e mined simul aneously wi h placing wo g oups o
geome ic en i ies. The p oblem a ises o ins ance in sol e s using i-
angle decomposi ion o educe he complexi y o he cons ain p ob-
lem.
This wo k offe s a se o basic cons uc i e me hods ha pe mi s o
de e mine a iable adius ci cles simul aneously wi h placing wo igid
geome ic objec s when geome ic cons ain s a e defined on bo h he
ci cum e ence and cen e poin o he cons ain ci cle. The p oblem
has been classified by he geome ic en i ies in wo g oups, one is fixed
and he o he has ansla ional and o a ional mo emen , so ha he
a iable adius ci cles sa is y he cons ain s on he geome ic en i ies
in hese wo g oups. The numbe o solu ions o each p oblem is also
gi en.
Keywo ds: Geome ic cons ain sol ing, a iable adius ci cles, con-
s uc i e sol e s, algeb aic sol e s, cyclog aphic maps.
1
1 In oduc ion
In cons ain -based geome ic design, he designe c ea es a ough ske ch o
an objec made ou o simple geome ic elemen s. Then he in ended exac
shape is specified by anno a ing he ske ch wi h cons ain s. A geome ic
cons ain sol e hen checks whe he he se o geome ic cons ain s cohe -
en ly defines he objec and, i so, de e mines he posi ion o he geome ic
elemen s.
Many echniques ha e been epo ed in he li e a u e ha p o ide pow-
e ul and efficien me hods o sol ing sys ems o geome ic cons ain s. Fo
example, see [2] and e e ences he ein o an ex ensi e analysis o wo k
on cons ain sol ing. Among hem, ou in e es ocuses on cons uc i e
echniques,
Cons uc i e sol e s ha e wo majo componen s: he analyze and he
cons uc o . The analyze symbolically de e mines whe he a geome ic
p oblem defined by cons ain s is sol able. I he p oblem is sol able, he
ou pu o he analyze is a sequence o cons uc ion s eps, known as he
cons uc ion plan, ha places each geome ic elemen in such a way ha
cons ain s a e sa isfied. A e assigning specific alues o he pa ame e s,
he cons uc o in e p e s he cons uc ion plan and builds an objec in-
s ance, p o ided ha no nume ical incompa ibili ies a ise.
The complexi y o geome ic cons ain sol ing is doubly exponen ial, a
ca ha de i es om he abili y o exp ess polynomial algeb aic equa ions
by geome ic cons ain configu a ions. As a esul , i is accep ed ha p ac-
ical sol e s a e no comple e, ha is, hey sol e a subclass o geome ic
p oblems.
A p ac ical use ul class o p oblems a e wodimensional cons ain p ob-
lems whe e he geome ic elemen s a e poin s, s aigh lines, and ci cles wi h
fixed adii, and in which he cons ain s a e like dis ance be ween wo poin s,
dis ance om a poin o a line, angle be ween wo lines, line-ci cle angency
and so on.
Va ious ex ensions o he geome ic epe oi e ha cons uc i e sol e s
can handle in wo dimensions can be conside ed. Exemples a e ci cles wi h
a iable adius, conics and B´ezie cu es. O hem, a iable adius ci cles
a e common cons uc s in wo dimensional cons ain sol ing and a e usually
no handled ully by cons uc i e sol e s. P obably hey a e he mos use ul
ex ension as hey pe mi auxilia y cons uc ion in addi ion, as explained
2
by Hoffmann and Ve mee , [9], Hoffmann and Joan-A inyo, [8], and Joan-
A inyo and So o, [10].
When he unde lying sol e is nume ical and good ini ial guesses a e
a ailable o he geome ic elemen s, a iable adius ci cles pose no pa ic-
ula p oblem. Bu he nume ical app oach o sol ing cons ain s has many
d awbacks, including eliance on good s a ing alues and he inabili y o
explo e solu ion a ian s, [2]. Wha is needed is a cons uc i e solu ion,
p e e able one in which he e is no need o sol e high-deg ee polynomials.
Recen ly, Hoffmann and Chiang, [6, 7], epo ed on an ex ension o he
basic cons uc s o deal wi h a iable adius ci cles in cons uc i e sol e s.
He e, he cons ain s on he a iable adius ci cle a e placed only on he
ci cum e ence.
In his wo k we u he ex end he basic cons uc ions o conside con-
s ain p oblems in which a iable adius ci cles occu wi h cons ain s de-
fined on hei cen e poin s.
The es o he pape is o ganized as ollows. In Sec ion 2 we gi e a sho
o e iew on ela ed wo k. Nex in Sec ion 3 we define a minimal se o ools
a use in e ace should p o ide o define a iable adius ci cles. Sec ion 4
ecalls he undamen al concep s o he cyclog aphic model geome y we
will make use o . Gene al algo i hms o he cons uc ions which sol e he
p oblem conside ed he e a e gi en in Sec ion 5. In Sec ion 6 we p esen
sol ing es a egies o keep o a minimum he complexi y o he algo i hms
implemen a ion. Finally we offe some conclusions in Sec ion 7.
2 P io Wo k
The e is a pauci y o published wo ks epo ing on a iable adius ci -
cles in cons uc i e geome ic cons ain sol ing. Ramana han, [14], s ud-
ied he Apollonious p oblem which consis s in cons uc ing a ci cle an-
gen o h ee gi en ci cles. The wo k add essed wo p oblems: De ising a
coo dina e-independen enume a ion me hod o he eigh possible solu ions
and pe o ming he compu a ions efficien ly. The echnique was applied o
cons ain -based, a iable adius fi ing o fille s o wo lines.
Joan-A inyo and So o desc ibed in [10] a hyb id echnique ha allows o
sol e cons ain p oblems in ol ing geome ic elemen s wi h mo e han wo
deg ees o eedom. In pa icula i is shown how he me hod sol es a iable
3
Co
e1
e2
e3
C(Co, )Rigid clus e
Figu e 1: Va iable adius ci cle C(C0, ) a ached o one clus e .
adius ci cles a ached o one geome ic objec which is de e mined up o
posi ion and o ien a ion, om now on e e ed o as a clus e [3], h ough
h ee cons ain s. See Figu e 1.
Hoffmann and Chiang ecen ly, [6, 7], epo ed on a mo e gene al ap-
p oach o cons uc i ely sol ing cons ain p oblems in ol ing a iable a-
dius ci cles. The app oach uses cyclog aphic maps, a special case o Lague e
geome y, [5], and handles he si ua ion whe e he a iable adius ci cle,
C(C0, ), (see Figu e 2) is a ached o wo clus e s, S1and S2,whichsha e
a common geome ic elemen , E. The o al numbe o deg ees o eedom
ha need o be canceled o S1,S2and he a iable adius ci cle o define
a clus e is ou : h ee o he ci cle i sel plus one due o he possible ela-
i e mo ion be ween S1and S2along E. These cons ain s a e canceled by
a aching he a iable adius ci cle o each clus e h ough wo cons ain s.
No e ha , o he wise he p oblem could be educed o he p e ious case. A
limi a ion o he me hod is ha i only conside s cons ain s placed on he
ci cum e ence o he a iable adius ci cle.
The DCM is a comme cial sol e , [1], which pe mi s sequen ial cons uc-
ions o a iable adius ci cles when hey a e a ached o one gi en clus e
h ough h ee cons ain s. As a as we know, [11, 12], no de ails ha e been
disclosed abou how he a iable adius ci cles a e handled.
3 De ini ion o Va iable Radius Ci cles
To define geome ic p oblems in ol ing ci cles wi h a iable adius, he use
in e ace should p o ide an app opia e se o ools. A minimal se o ools
4
Co
e
e11
e12
e1m
e21 e22
S1
C(Co, )
S2
e2n
Figu e 2: Va iable adius ci cle C(C0, ) a ached o wo clus e s.
would include an explici command o igge he a iable adius ci cle de -
ini ion along wi h ope a ions o place geome ic cons ain s on i s ci cum-
e ence and on i s cen e .
We assume ha he geome ic elemen s om which cons ain p oblems
a e buil a e poin s, s aigh lines and ci cles. A sufficien se o cons ain s
o define a iable adius ci cles includes angencies and dis ances.
3.1 Cons ain s Placed on he Ci cum e ence
We define he angency cons ain s placed on he ci cum e ence as ollows.
See Figu e 3. The ci cum e ence o he a iable adius ci cle can be angen
o
P
Qo
C
Co d
d
d
on
LQ
Figu e 3: Cons ain s placed on he ci cum e ence o a a iable adius ci cle.
5

•The ci cum e ence o a fixed adius ci cle.
•A s aigh line.
•A poin . This is he usual on cons ain .
Dis ance cons ain s placed on he ci cum e ence o he a iable adius ci cle,
see Figu e 3, a e defined as ollows
•Dis ance o a fixed adius ci cle Q: The minimum dis ance be ween
he wo ci cles measu ed along he s aigh line defined by hei cen e
poin s.
•Dis ance o a s aigh line L: The minimum dis ance be ween he
ci cle and he line measu ed along he pe pendicula o he gi en line
h ough he ci cle cen e poin .
•Dis ance o a poin P: Dis ance be ween he ci cle and he poin
measu ed along he s aigh line defined by he poin and he cen e
o he ci cle.
3.2 Cons ain s Placed on he Cen e Poin
Cen e poin s o a iable adius ci cles ha e no p i ileges o e o he poin s.
The e o e he se o cons ain s ha apply o gene ic poin s apply also o
cen e poin s o ci cles wi h a iable adius. We assume ha he cons ain s
a ailable a he use in e ace a e, see Figu e 4,
•The cen e poin can be a a gi en dis ance om ano he geome ic
elemen .
•The cen e poin can be on ( angen o) ano he geome ic elemen .
To acili a e he use in e ac ion, o he cons ain s could be added o he
epe oi e so a p esen ed.
4 The Cyclog aphic Model
Se e al geome ic design p oblems can be sol ed in a su p isingly simple
way i one uses Lague e geome y. A specific case o his geome y, known
6
P
Qo
C
Co
don
on
LQ
on
dd
Figu e 4: Cons ain s placed on he cen e o a a iable adius ci cle.
as he cyclog aphic model, esul s pa icula ly use ul o sol e he p oblem
we ha e a hand, [14].
Fo he sake o comple ness, we ecall he undamen al concep s o he
cyclog aphic model o he embedding o space R2in R3we will make use
o . Fo a gene al and mo e in dep h discusion on he cyclog aphic model
and i s applica ions o compu e aided geome ic design see Hoffmnann [5],
and Po mann and Pe e nell [13].
The undamen al elemen s in R2we conside a e ays and cycles.A ay
is an o ien ed s aigh line. A cycle is an o ien ed ci cle o a poin (cycle
wi h adius 0). The o ien a ion is fixed by a uni no mal ec o field in he
case o ays and by a signed adius in he case o he cycle.
The basic ela ion is ha o o ien ed con ac be ween cycles and ays.
Re e o Figu e 5. An o ien ed cycle and a ay a e in o ien ed con ac , i
hey a e angen and he uni no mals coincide a he poin o con ac . Fo
a poin and a ay, o ien ed con ac equals incidence.
L
C
ab
L
C
Figu e 5: Con ac ay-cycle. a) O ien ed. b) No o ien ed.
7
γ
C
a
π/4
C
(a, b)
b
π/4
π/4
P
γ
P
Figu e 6: Cyclog aphic maps. a) Cycle. b) Poin .
Le C(a, b, ) deno e a cycle wi h cen e poin (a, b) and signed adius
. We assume ha when >0, he cycle is o ien ed coun e clockwise; i
<0, he cycle is o ien ed clockwise. When = 0, he cycle ep esen s a
poin and is conside ed o ha e bo h o ien a ions simul aneously.
Wi h each cycle C(a, b, ) he e is an associa ed cyclog aphic map,de-
no ed by γC, defined as he cone whose apex is he poin (a, b, )inR3,
whose axis is pa allel o he Zaxis and whose angle is equal o π/4. Fig-
u e 6 illus a es his concep .
Conside he line in R2whose equa ion is ax +by +c=0. No e ha ,
depending on he o ien a ion, a s aigh line can suppo wo diffe en ays.
The o ien a ion o a ay, gi en by i s di ec ion ec o , is defined as he ec o
[b, −a]; ha is, he esul o o a ing clockwise by 90◦ he ec o [a, b], which
is no mal o he line. We shall deno e a ay by L(a, b, c)o jus L.
Wi h each ay L(a, b, c) he e is an associa ed cyclog aphic map, deno ed
by γL, defined as he plane in R3which in e sec s he XY plane a Land
a an angle wi h [b, −a]equal oπ/4. See Figu e 7.
n
LL
π/4
γ
L
Figu e 7: Cyclog aphic map o a ay.
8
The dis ance o a poin o a ay is measu ed as a posi i e quan i y i
he poin is o he le o he ay as seen in he ay’s o ien a ion. The
angle be ween a pai o ays, ∠(Li,L
j) is measu ed om he di ec ion o Li
clockwise o he di ec ion o Lj.
5 Sol ing Va iable Radius Ci cles
The se o cons ain s gi en in Sec ion 3 e e o he ools a ailable a he use
in e ace o p o ide a iendly in e ac ion. To acili a e he sol ing p oces, we
fi s show how o ans o m he p oblem defined a he use in e ace in o an
equi alen p oblem, whe e dis ance cons ain s on he a iable adius ci cle
a e exp essed as angencies.
Nex , o handle he cons ain s defined on he cen e poin o a iable
adius ci cles in a uni o m and consis en way, we ex end he cyclog aphic
model wi h wo new auxilia y maps.
Then we gi e gene al algo i hms ha compu e a iable adius ci cles ha
a e a ached o wo igid clus e s h ough cons ain s placed on bo h, he
ci cum e ence and he cen e poin o he ci cle. Following [6, 7], we conside
wo diffe en scena ios: 1) The geome ic elemen Esha ed by clus e s S1
and S2, see Figu e 2, is a s aigh line and ela i e mo ion is ansla ional,
and 2) Eis a ci cle o poin and he ela i e mo ion o clus e s is a o a ion.
5.1 P oblem T ans o ma ion
Fi s we conside he dis ance cons ain s placed on he ci cum e ence o he
a iable adius ci cle o be de e mined, C(C0, ). The ci cle-line dis ance
cons ain , dis(C, L)=d, see Figu e 8, is equi alen o a angency cons ain
be ween he ci cle Cand a line Lwhich has been ansla ed a dis ance d
along i s no mal. Le Q(Q0, ) be a ci cle wi h cen e Q0andfixed adius
. he dis ance cons ain dis(C, Q(Q0, )) = dis ans o med in o he an-
gency cons ain (C, Q(Q0, +d)). Finally, he dis ance cons ain be ween
Cand poin P,dis(C, P)=d, is ans o med in o he equi alen angency
cons ain (C, Q(P,d)).
Dis ance cons ain s placed on he cen e poin C0o C(C0, )a e ans-
o med in o angency (on) cons ain s as ollows. The cen e poin -poin
dis ance, dis(C0,P)=dis ans o med in o (C0,Q(P,d)). The cen e
poin -line cons ain dis(C0,L)=dis ans o med in o (C0,L
), whe e L
9
P oblem 2cons ain s 1cons ain
E1: E(LL,LL)(1,4) E11: E(LL,L’L’)(1,2) E13: E(LL,LL’)(1,2)
E12: E(LL’,LL’)(1,2)
E2: E(CL,LL)(2,8) E21: E(CL,L’L’)(2,4) E25: E(CL,LL’)(2,4)
E22: E(CL’,LL’)(2,4) E26: E(CL’,LL)(2,4)
E23: E(C’L,LL’)(2,4) E27: E(C’L,LL)(2,4)
E24: E(C’L’,LL)(2,4)
E3: E(CL,CL)(4,16) E31: E(CL,C’L’)(4,8) E35: E(CL,CL’)(4,4)
E32: E(CL’,CL’)(4,4) E36: E(CL,C’L)(4,16)
E33: E(C’L,CL’)(4,16)
E34: E(C’L,C’L)(4,4)
E4: E(CC,LL)(4,16) E41: E(CC,L’L’)(2,4) E44: E(CC,LL’)(2,4)
E42: E(CC’,LL’)(4,16) E45: E(CC’,LL)(4,16)
E43: E(C’C’,LL)(2,4)
E5: E(CC,CL)(8,32) E51: E(CC,C’L’)(4,8) E55: E(CC,CL’)(4,4)
E52: E(CC’,CL’)(8,16) E56: E(CC,C’L)(4,16)
E53: E(CC’,C’L)(8,16) E57: E(CC’,CL)(8,16)
E54: E(C’C’,CL)(4,8)
E6: E(CC,CC)(16,64) E61: E(CC,C’C’)(4,8) E63: E(CC,CC’)(8,16)
E62: E(CC’,CC’)(16,64)
Table 1: Gene al me ge p oblem classifica ion.
we will deno e by Land C he geome ic elemen s in a me ge p oblem on
which cen e cons ain s ha e been defined. Fo example C(LL,CL) will
deno e ha one line in he fixed clus e and he ci cle in he mo ing clus e
suppo cen e cons ain s wi h espec o he a iable adius ci cle.
A gene al classifica ion o he ansla ional and o a ional me ge p ob-
lem is shown in Table 1. The fi s column indica es he p oblems wi h
ci cum e ence cons ain s only, he second and hi d columns show he di -
e en p oblems wi h wo and one cen e cons ain s espec i ely. The pai
(m, n) a e each p oblem indica es he maximum numbe o solu ions, m
o ansla ional and n o o a ional p oblems. We will explain la e on how
hese figu es ha e been de i ed.
16

6.2 Deg ee o he Equa ions
To simpli y he p oblem, we assume ha in he ansla ional case he s aigh
line sha ed by he clus e s is coinciden wi h he X-axis and ha in he
o a ional p oblem he cycle sha ed by he clus e s is cen e ed a he o igin.
Using he no a ion al eay in oduce in Sec ion 5 and wi h simple geom-
e y, we ha e he ollowing heo em
Theo em 6.1 The equa ions o γL,τL,γL(d), and τL(d) a e deg ee one.
The equa ions o γC,τC,γC(d), τC(d), γL(θ), and τL(θ) a e deg ee wo.
And, he equa ions o γC(θ)andτC(θ) a e deg ee 4 equa ions.
No ice ha he equa ions o γL,τL,γC and τC ha e 3 a iables x, y, z,
and he equa ions o γL(d), τL(d), γC(d), τC(d), γL(θ), τL(θ), γC(θ)and
τC(θ) add one mo e a iable, d.
As men ioned in Sec ion 5, he a iable adius ci cle can be ound by
in e sec ing ou su aces, each su ace being a γ-map o a τ-map, depend-
ing on whe he he cons ain on he a iable adius cycle is a ci cum e ence
cons ain o a cen e cons ain . The sys em o equa ions can be easily gen-
e a ed by gene a ing he equa ions o he maps associa ed o each geome ic
elemen in ol ed. Fo example, he solu ion o he p oblem L(CL,CL)can
be figu ed ou by finding he in e sec ion
γC1∩τL
2∩τC
3(d)∩γL4(d)
Since equa ions τL
2,andγL4(d) a e deg ee one and γC1and τC
3(d)a e
deg ee wo equa ions, om Bezou ’s heo em, [4], we know he e a e 4 so-
lu ions o his sys em. By using Bezou ’s heo em, e e y subp oblem Eij
o p oblem Ei, see Table 1, has he same numbe o solu ions. Fo example,
e e y subp oblem o L1, including L11,L12 and L13, has only one solu ion,
and e e y subp oblem o C1, including C11,C12 and C13, has ou solu-
ions. The numbe o solu ions o each p oblem is summa ized in Table 1.
In he ollowing sec ion, we will de i e s a egies o each me ge p oblem
subclass o educe hese numbe s o compu e a a iable adius ci cle.
No ice ha he numbe o solu ions gi en is based on ou app oach
by using he γcyclog aphic maps and τmaps. I we do no use hese
maps, he numbe o solu ions mus be mul iplied by 8, he numbe o
essen ially dis inc o ien a ions o lines and cycles. Fo example, he numbe
o solu ions o he p oblems L(LL, LL)andC(LL, LL) would be 8 and 32,
espec i ely.
17
6.3 Algo i hms o he T ansla ional Me ge P oblem
The subp oblems gi en in Table 1 a e indi idualized as ansla ional me ge
p oblems by eplacing Eij wi h Tij. To de i e s a egies o educe he de-
g ee o he equa ions o be sol ed, we g oup he ansla ional me ge p oblems
in ol h ee diffe en classes as ollows:
1. P oblems wi h wo cen e cons ain s defined in he same clus e . This
includes T11, T21, T24, T31, T41, T43, T51, T54 and T61.
2. P oblems ha can be ans o med in o he in e sec ion o h ee planes
and one su ace. This includes T12, T13, T22, T23, T25, T26, T27,
T32, T34, T35, T44, T55, and pa o he p oblems in he p e ious
class.
3. P oblems ha can be ans o med in o he in e sec ion o one γC,one
τC, and wo planes. This includes T33, T36, T42, T45, T52, T53,
T56, T57, T62 and T63.
In he ollowing h ee subsec ions we p esen , om easy o ha d, he
solu ion o he p oblems lis ed abo e.
6.3.1 Two cen e cons ain s in he same clus e
This p oblem can be sol ed by o cing he clus e wi h wo cen e cons ain s
o be he mo ing clus e , so he p oblem becomes L(E1E2,E
3E
4). No ice
ha i he mo ing clus e has wo cen e cons ain s he clus e fixed has
no cen e cons ain s. F om he ac ha he cone-cone in e sec ion can
be ans o med in o cone-plane in e sec ion, [6, 7], he in e sec ion o he
geome ic elemen s in he fi s clus e can always be ep esen ed by he
in e sec ion o he map o he fi s elemen E1wi h a fixed plane. The
algo i hm o sol e he p oblem is:
Algo i hm L(E1E2,E
3E
4)
1. Find he poin (x, y)=τE
3∩τE
4.
2. Subs i u e he poin (x+d, y) in o he equa ion o he plane
gene a ed in he fi s clus e and find z(d)whichisadeg ee
one equa ion o a iable d.
3. Subs i u e he poin (x+d, y, z(d)) in o he equa ion o E1
o yield one equa ion in d.
18
4. Sol e he equa ion o find he alue o d.
5. The a iable adius ci cle seeked has (x+d, y)
as cen e poin and z(d)as adius.
The ollowing h ee heo ems gi e he ools needed o figu e ou he
in e sec ion o τE
3and τE
4. The fi s heo em is i ial and applies when
bo h E
3and E
4a e s aigh lines.
Theo em 6.2 Two diffe en s aigh lines Li=[ai,b
i,e
i]andL2=[aj,b
j,e
j]
which a e no pa allel, in e sec a poin
(−eibj+ejbi,−aiej+ajei,a
ibj−ajbi)
The second heo em educes he line-ci cle in e sec ion o wo line-line
in e sec ions.
Theo em 6.3 Le L=[a, b, e] be a s aigh line and C=(x, y, )aci cle.
In e sec ing Land Cis equi alen o in e sec ing Land L=[a,b
,e
]whe e
a=a(2 )+b(1 − 2)
b=−a(1 − 2)+b(2 )
e=−M(1 − 2)−N(2 )
and
=±−(ax +by +e− )/(ax +by +e+ )
M=bx −ay
N=ax +by
Fu he mo e, he in e sec ion poin s a e (Ax+Cx , Ay+Cy , 1) whe e
Ax=bM −ae, Cx=b 2−(N+e)2
Ay=−aM −be, Cy=−a 2−(N+e)2
No ice ha is eal i and only i − ≤ax +by +d≤ and ha each
diffe en alue o ep esen s a diffe en line.
No ice u he ha when in e sec ing a ci cle Cwi h a line L(d)=
[a, b, e−ad], he abo e heo em applies jus eplacing eby e−ad o eplacing
19
xby x−d. In his case, he ela ion be ween and dbecomes ad(1 − 2)=
(e− )(1 − 2)+N(1 + 2).
The hi d heo em ans o ms he in e sec ion o wo ci cles in o a line-
ci cle in e sec ion.
Theo em 6.4 Le Ci=(xi,y
i,
i)andCj=(xj,y
j,
j)be woci cles.
In e sec ing Ciand Cjis equi alen o in e sec ei he ci cle Cio Cjwi h
he line L=[a, b, e]whe e
a=xj−xi
b=yj−yi
e=1
2(x2
i+y2
i− 2
i−x2
j−y2
j+ 2
j)
The numbe o solu ions in each case can be easily calcula ed. Two lines
in e sec a mos in one poin and a line and a ci cle o wo ci cles in e sec
a mos in wo poin s. I he clus e fixed has wo cycles, we can ans o m
he in e sec ion o hei cyclog aphic maps in o he in e sec ion o one cone
wi h a plane, which has wo equa ions o deg ee one. This inc eases he
numbe o solu ions by a ac o o 2. The e o e, he e is one solu ion o
T11, wo solu ions o T21, T24, T41, T43, and ou solu ions o T31, T51,
T54 and T61.
6.3.2 In e sec ion o h ee planes and one su ace
In [6, 7], cone-cone in e sec ions a e ans o med in o cone-plane in e sec-
ions. Le Π(C1,C
i) deno e he plane ha con ains he in e sec ion cu es
o he cones γC1and γCio τC1and τCi. an conside , o example, he
subp oblem E(CC,CC). Fi s h ee planes, namely Π(C1,C
2), Π(C1,C
3)
and Π(C1,C
4) a e in e sec ed. Then his in e sec ion is subs i u ed in he
map γC1. We apply his app oach he e o find he in e sec ion o ou cones,
wi h he deg ee o eedom ha he hi d and ou h cones mo e along he
X-axis o o a e abou he o igin. We use he simila app oach o sol e he
p oblem in his c i e ion. No ice ha he in e sec ion o τC1and τC2can
be con e in o he in e sec ion o τC1wi h a plane τL.
Table 2 summa izes he p oblems we conside he e. The hi d, ou h
and fi h columns gi e he planes, gene a ed as γand τmaps, whose common
poin defines he dis ance d ha he mo ing clus e mus be ansla ed along
he X-axis. This common poin is hen subs i u ed in he equa ion gi en in
20
P oblem Equa ion Π1Π2Π3Deg ee
T12: L(LL’,LL’) γL1τL
2γL3(d)τL4(d) 1
T13: L(LL,LL’) γL1γL2γL3(d)τL4(d) 1
T22: L(CL’,LL’) γC1τL2γL3(d)τL4(d) 2
T23: L(C’L,LL’) γC
1γL2γL3(d)τL4(d) 2
T25: L(CL,LL’) γC1γL2γL3(d)τL4(d) 2
T26: L(CL’,LL) γC1τL2γL3(d)γL4(d) 2
T27: L(C’L,LL) τC
1γL2γL3(d)γL4(d) 2
T32: L(CL’,CL’) γC1τL2P(C1,C
3(d)) τL4(d) 4
T34: L(C’L,C’L) τC
1γL2P(C
1,C
3(d)) γL4(d) 4
T35: L(CL,CL’) γC1γL2P(C1,C
3(d)) τL4(d) 4
T44: L(CC,LL’) γC1P(C1,C
2)γL3(d)τL4(d) 2
T55: L(CC,CL’) γC1P(C1,C
2)P(C1,C
3(d)) τL4(d) 4
Table 2: Classifica ion o he h ee planes and one su ace in e sec ion p ob-
lem.
he second column, yielding an equa ion on he a iable dwhose deg ee is
shown in he las column. The specific algo i hm o sol e he p oblem can
be w i en as ollows.
Algo i hm L(E1E2,E
3E4)
1. Find he poin (x(d),y(d),z(d),w(d)) = Π1∩Π2∩Π3.
2. I ci cum(E1,C) hen
M:= γE1
else i cen e (E1,C) hen
M:= τE
1
endi
3. Gene a e one equa ion wi h one a iable dby eplacing
(x(d),y(d),z(d),w(d)) in he equa ion o M.
4. Sol e he sys em o equa ions o find a iable d.
5. The a iable adius ci cle seeked has (x(d)/w(d),y(d)/w(d))
as cen e poin and z(d)/w(d)as adius.
6.3.3 In e sec ion o one γ-cylinde one τ-cylinde and wo planes
The Table 3 summa izes he p oblems we conside in his sec ion. These
p oblems a e ans o med in o he in e sec ion o wo planes wi h a cone,
21

P oblem γC τCΠ1Π2Deg 1 Deg 2 Deg ee
T33: L(CL,CL)γC1τC
3(d)τL2γL4(d)(1,1,0) (0,0,0) 4
T36: L(CL,CL)γC1τC
3(d)γL2γL4(d)(1,1,0) (0,0,0) 4
T42: L(CC,LL
)γC1τC
2γL3(d)τL4(d)(1,0,0) (0,0,0) 4
T45: L(CC,LL)γC1τC
2γL3(d)γl4(d)(1,0,0) (0,0,0) 4
T52: L(CC,CL
)γC1τC
2dP(C1,C
3(d)) τ(L4(d)) (2,2,0) (0,0,1) 8
T53: L(CC,CL)γC1τC
2P(C
2,C
3(d)) γL4(d)(2,2,0) (0,1,1) 8
T56: L(CC,CL)γC1τC
3(d)P(C1,C
2)γL4(d)(1,1,0) (0,0,0) 4
T57: L(CC,CL)γC1τC
2P(C1,C
3(d)) τL4(d)(2,2,0) (0,1,1) 8
T62: L(CC,CC)γC1τC
2P(C1,C
3(d)) P(C
2,C
4(d)) (2,3,0) (0,1,1) 18(16)
T63: L(CC,CC)γC1τC
2P(C1,C
3(d)) P(C3,C
4)(d)(2,2,0) (0,1,1) 8
Table 3: Classifica ion o he γC,τCand wo planes in e sec ion p oblem.
γC, and a cylinde , τC. The planes Π1and Π2, a e gi en in he ou h and
fi h columns, he second column lis s he γmap and he hi d column he
τmap.
No e ha when he mo ing clus e is ansla ed along he X-axis, he
line common o planes Π1and Π2defines he dis ance d. Assume ha
Π1=(a1(d),b
1(d),c
1(d),w
1(d))
and
Π2=(a2(d),b
2(d),c
2(d),w
2(d))
a e wo planes in Table 3, he pa ame ic o m o he line whe e Π1and Π2
in e sec is
L=(a1(d),b
1(d),c
1(d),w
1(d)) + s(a2(d),b
2(d),c
2(d),w
2(d))
The deg ees on he a iable do each componen in (a1(d),b
1(d),c
1(d)) and
(a2(d),b
2(d),c
2(d)) a e shown in he six h and se en h column in Table 3.
The algo i hm o finding he solu ion o his class o p oblems is he ol-
lowing
Algo i hm L(CE2,E
3E4)
1. Acco ding o he subp oblem a hand and ollowing Table 3,
gene a e γC,τC,Π
1and Π2)
2. Find he pa ame ic o m o he line L=Π
1∩Π2.
3. Gene a e wo equa ions in dand sby subs i u ing he
explici o m o L in o he implici o ms o γC and τC.
22
4. Figu e ou dby sol ing he sys em o wo equa ions de i ed
in s ep 3.
5. Poin (a1(d),b1(d)) + s(a2(d),b2(d)) is he cen e o he
a iable adius ci cle and c1(d)+s∗c2(d) is he adius.
Applying Bezou ’s heo em o he equa ions de i ed in s ep 3 in he
Algo i hm L(CE2,E
3E4), we find he maximun numbe o solu ions o he
p oblem, which is gi en in he eigh column o Table 3. No ice ha compa ed
o he sys em o equa ions gene a ed in Sec ion 6.2, his app oach yields 2
mo e solu ions o he p oblem L(CC,CC).
6.4 Algo i hms o he Ro a ional Me ge P oblem
The classifica ion o o a ional clus e s is he same as in he ansla ional
case. All wha is needed is o eplace Eij wi h Rij in Table 1 o indica e
ha he p oblem has he same cons ain pa e n bu he mo ing clus e is
now o a ed. We also sepa a e hese p oblems in o h ee diffe en classes.
They a e:
1. P oblems wi h wo cen e cons ain s defined in he same clus e . This
includes R11, R21, R24, R31, R41, R43, R51, R54 and R61.
2. P oblems which can be ans o med in o he in e sec ion o h ee
planes and one su ace. This includes R12, R13, R22, R23, R25, R26,
R27, R32, R34, R35, R44, R55, and pa o he p oblems in he p e-
ious class.
3. The emainde o he p oblems, including R33, R36, R42, R45, R52,
R53, R56, R57, R62, R63.
6.4.1 Two cen e cons ain s in he same clus e
I he clus e wi h wo cen e cons ain s is he one ha will be o a ed, he
p oblems in his class a e o mally sol ed in he same way as L(E1E2,E
3E
4).
The in e sec ion o he geome ic elemen s in he clus e fixed can always
be ep esen ed by he in e sec ion o he map o he fi s elemen E1wi h
afixedplane. I θis he o a ion angle and = an(θ/2) he algo i hm o
sol e he p oblem is
23
Algo i hm C(E1E2,E
3E
4)
1. Find he poin (x, y)=τE
3∩τE
4.
2. Ro a e he poin (x, y)byanangleθyielding (x( ),y( )).
3. Replace (x( ),y( )) in o he equa ion o he plane gene a ed
in he fi s clus e and find z( ) which is a deg ee one
equa ion in .
4. Subs i u e (x( ),y( ),z( )) in o he equa ion o E1 o yield
one equa ion in .
5. Sol e he equa ion o find he alue o .
6. The seeked ci cle is cen e d on (x( ),y( )) and z( ) is he adius.
6.4.2 In e sec ion o h ee planes and one su ace
P oblems in his class, C(E1E2,E
3E4), a e sol ed as p oblems in he co e-
sponding ansla ional class L(E1E2,E
3E4) eplacing he ansla ion wi h
he o a ion αI = an(θ/2), he algo i hm is
Algo i hm C(E1E2,E
3E4)
1. Find he poin (x( ),y( ),z( ),w( )) = Π1∩Π2∩Π3.
2. I ci cum(E1,C) hen
M:= γE1
else i cen e (E1,C) hen
M:= τE
1
endi
3. Gene a e one equa ion wi h one a iable by eplacing
(x( ),y( ),z( ),w( )) in he equa ion o M.
4. Sol e he sys em o equa ions o find a iable .
5. The a iable adius ci cle seeked has (x( )/w( ),y( )/w( ))
as cen e poin and z( )/w( )as adius.
To jus i y he deg ee educ ion, we need he ollowing esul .
Theo em 6.5 Conside h ee planes wi h cons an coefficien s excep o :
Π1=[a2,b
2,c
2,−d2]
Π2=[a3(1 − 2)−b3(2 )+e3(1 + 2),a
3(2 )+b3(1 − 2)+ 3(1 + 2),
c3(1 + 2),−d3(1 + 2)]
Π3=[a4(1 − 2)−b4(2 )+e4(1 + 2),a
4(2 )+b4(1 − 2)+ 4(1 + 2),
c4(1 + 2),−d4(1 + 2)]
24
Then Π1,Π2and Π3in e sec in a poin (x( ),y( ),z( ),w( )) whose com-
ponen s a e exp essions o deg ee 2 in .
Now i is easy o show ha p oblems in his class ha e wo solu ions
when he fi s componen E1is a ay, such as in p oblems C12 and C13.
O he wise, hey ha e 4 soul ions, such as in p oblems C22, C23, C25, C26,
C27, C32, C34, C35, C44 and C55. The numbe o solu ions is gi en in he
Table 1.
6.4.3 Remainde P oblems
The emainde subp oblems o o a ional me ge p oblems a e C33, C36,
C42, C45, C52, C53, C56, C57,C62 and C63.
Un o una ely, he s a egy p esen ed in Sec ion 6.3 does no wo k he e
because he deg ee o he pa ame ic line gene a ed a an in e media e s ep
does no allow o educe he final deg ee o γC and τC.
We need o de i e some esul s be o e p esen ing ou algo i hm. Le C
be a cycle cen e ed a (x1,y
1)wi h(signed) adiusz1and le Land Lbe
ays wi h equa ions a2x+b2y+d2=0,anda2
2+b2
2= 1 espec i ely. Le
δ=(a2,b
2,d
2)·(x1,y
1,1) = (a2x1+b2y1+d2).
Theo em 6.6 The in e sec ion poin s o γC and γL a e gi en by
⎧
⎪
⎨
⎪
⎩
x(u)=x1+z11−u2
1+u2−δ
w(u)(1 −u2)
y(u)=y1+z12u
1+u2−δ
w(u)(2u)
z(u)=2z1−δ
w(u)(1 + u2)
No ice ha when z1= 0, he locus o he in e sec ion poin s in he abo e
heo em can be w i en in homogeneous o m as:
⎧
⎪
⎪
⎨
⎪
⎪
⎩
x(u)=x1w(u)−δ(1 −u2)
y(u)=y1w(u)−δ(2u)
z(u)=δ(1 + u2)
w(u)=(a2,b
2,−1) ·(1 −u2,2u, 1+u2)
Theo em 6.7 The in e sec ion poin s o γC and τLa e
⎧
⎪
⎪
⎨
⎪
⎪
⎩
x(u)=x1w(u)−δ(1 −u2)
y(u)=y1w(u)−δ(2u)
z(u)=z1w(u)−δ(1 + u2)
w(u)=(a2,b
2,0) ·(1 −u2,2u, 1+u2)
25
whe e Π = [x1−x0,y
1−y0,z
0−z1,(x2
0+y2
0−z2
0−x2
1−y2
1+z2
1)/2].
Theo em 8.12 The cyclog aphic map o he ay [a, b, d] o a ed abou he
o igin by θhas he o m
[a(1 − 2)−b(2 ),a(2 )+b(1 − 2),c(1 + 2),d(1 + 2)]
whe e = an(θ/2), −π<θ<π,andc=−√a2+b2.Whenθ=π, he
cyclog aphic map becomes [−a, −b, c, d].
Theo em 8.13 Le L=[a, b, d]bea ay.ThemapsγL(θ)andτL(θ)ha e
he o m
[a(1 − 2)−b(2 )+e(1 + 2),a(2 )+b(1 − 2)+ (1 + 2),c(1 + 2),d(1 + 2)]
whe e = an(θ/2), −π<θ<π,e= =0,andc=−√a2+b2,c=0
o he γL(θ)andτL(θ) espec i ely. When θ=π, heγL(θ)andτL(θ)
becomes [−a, −b, c, d].
Theo em 8.14 Le C
1=(x1,y
1,z
1)andC
3=(x3,y
3,z
3). The in e sec ion
plane o τC
1and τC
3(θ) has he o m
[a(1 − 2)−b(2 )+e(1 + 2),a(2 )+b(1 − 2)+ (1 + 2),c(1 + 2),d(1 + 2)]
whe e = an(θ/2), −π<θ<π,a=x3,b =y3,e =−x1, =−y1,c =0,
and d=(x2
1+y2
1−z2
1−x2
3−y2
3+z2
3)/2. When θ=π, he cyclog aphic map
becomes [−a+e, −b+ ,0,d].
32