close

Вход

Забыли?

вход по аккаунту

1227161

код для вставки
Représentation géométrique des arrangements de droites
du plan
Guillaume Allègre
To cite this version:
Guillaume Allègre. Représentation géométrique des arrangements de droites du plan. Modélisation
et simulation. Université Joseph-Fourier - Grenoble I, 2003. Français. �tel-00004631�
HAL Id: tel-00004631
https://tel.archives-ouvertes.fr/tel-00004631
Submitted on 11 Feb 2004
HAL is a multi-disciplinary open access
archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d’enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
THÈSE
présentée par
Guillaume A LLÈGRE
pour obtenir le titre de
Docteur de l’université Joseph Fourier - Grenoble I
Spécialité : Mathématiques appliquées
Représentation géométrique
des arrangements de droites du plan
soutenue le 17 novembre 2003
Composition du jury :
–
–
–
–
–
M. Georges-Pierre B ONNEAU, président
M. Dominique M ICHELUCCI, rapporteur
M. Jean-Claude YAKOUBSOHN, rapporteur
M. Bernard L ACOLLE, directeur
M. Nicolas S ZAFRAN, examinateur
Thèse préparée au sein du laboratoire LMC-IMAG, équipe MGA
! " # $%&!
% ! " ' () !
*
+ + () + ! ( + ' (+
# )+ # &, -
% - -! $ &, + ( ( + . ( % - &, ' !
! / ! % + ) + 0
'-!
1 2
!!!
3!3
3!
3!2
3!6
/1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
3
3!3!3
+ (- ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
3
3!3!
+ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
3
'# + ! ! ! ! ! ! ! !
3!!3
0 '# ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
3!!
4 '# ! ! ! ! ! ! ! !
2
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
6
3!2!3
4 + ( ! ! ! ! ! ! ! ! !
6
3!2!
4 + ! ! ! ! ! !
6
3!2!2
5 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
7
3!2!6
/ 1 ! ! ! ! ! ! ! ! ! ! ! ! !
7
/ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
28
3!6!3
# ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
28
3!6!
9( ) : ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
22
3!6!2
/ + 22
0 +
5 +
6
! ! ! ! ! ! ! !
!3
!
!2
0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
2;
!3!3
0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
2;
!3!
< ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
68
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
68
!!3
+ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
68
!!
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
6
!!2
0
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
66
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
6=
!2!3
0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
6=
!2!
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
6;
0 2!3
2!
2!2
2!6
' > 1 ! ! ! ! ! ! ! ! ! ! !
??
2!3!3
0 1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
[email protected]
2!3!
/ > + 1+ ?7
( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
?=
2!!3
+ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
?=
2!!
. > ! ! ! ! ! ! ! ! ! ! ! !
?;
2!!2
< A ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
@8
B + ! ! ! ! ! ! ! ! ! ! ! ! ! !
@3
2!2!3
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
@3
2!2!
+ ! ! ! ! ! ! ! ! ! ! ! !
@
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
@7
2!6!3
C ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
@7
2!6!
< ) ! ! ! ! ! ! ! ! ! ! ! ! !
@7
2!6!2
0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
@;
?
!
6!3
( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
7;
6!
) + ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
7;
6!!3
/ : + ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
=8
6!!
4)+ + ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
=3
6!!2
5 ( @ =
! ! ! ! ! ! ! ! ! ! ! ! ! ! !
" #
?!3
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;3
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;3
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;
) + µ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;2
?!!3
/1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;2
?!!
) µ ' 4+
! ! ! ! ! ! ! ! ! ! !
;2
+ λ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;=
?!2!3
/1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;=
?!2!
λ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
;=
?!2!2
< λ + ! ! ! ! ! ! !
388
?!6
/ ) E ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
388
?!?
< ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
383
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
383
?!
?!2
[email protected]
)
?!3!3
D ?!3!
)
) ?!?!3
?!?!
/ : ! ! ! ! ! ! ! ! ! ! ! ! ! !
38
?!?!2
( + ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
382
?!?!6
+ ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
386
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
38?
F @
$
@!3
@!
< > %
! ! ! ! ! ! 333
@!3!3
n = 4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 333
@!3!
n = 5 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 33?
+ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 337
@!!3
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 337
@!!
4 + ! ! ! ! ! ! ! 33;
@!!2
+ ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 33
& '
7
3!;
n = 3 ! ! ! !
n = 3 ! ! ! !
!
! ! ! ! ! ! !
!"
# ! $ % " & ' ( $ ) % * D4 A(D1 , D2 , D3 )+ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
# ' ! ! ! ! ! ! ! ! !
!3
∆
3!3
3!
3!2
3!6
3!?
[email protected]
3!7
3!=
!
!2
!6
2!3
2!
2!2
2!6
2!?
[email protected]
Ol % , ! ! ! !
- Dk ! ! ! ! ! ! ! ! ! ! ! ! !
& .
( $ ! ! ! !
?
?
@
=
;
2
22
[email protected]
! !
62
! !
6?
! !
[email protected]
! !
67
R3 + z = −1 ! !
/ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
- ) 0, ! ! ! ! ! ! !
- , ) 1 0 , ! ! !
2 # (# 3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
=
2
??
?;
@2
@@
@=
76
6!3
6!
6!2
6!6
6!?
[email protected]
6!7
?!3
?!
?!2
?!6
?!?
[email protected]
?!7
?!=
?!;
?!38
?!33
!"
# ! $ % " (# 4 p = (7, 12, 3, 0, 0) ! ! !
5 $ 6 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
01 7 8 p = (6, 9, 0, 1) ) 4
7 # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
09 7 88 p = (6, 8, 2, 0) # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
0 7 888 p = (7, 6, 3, 0) # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
, 7 8: p = (10, 0, 6, 0) # # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
! " . ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
$ Di ai < 0, bi > 0, di < 0 ! ! ! ! ! ! !
;# . µ 5 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
(# ! ! ! ! ! ! ! ! ! !
# / ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
3 0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
3 , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
% ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
( * < ! ! !
( * < ) ! !
= 4 ) % λ = 0, 0031 λ = 0, 0603 9 ×20 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
?!3
?!32
= 0, ) % λ = 0, 0023 λ = 0, 0141 ' =8
=3
=
=2
=?
[email protected]
=7
;3
;
;2
;6
;?
;@
;7
;=
38
382
[email protected]
×6 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
387
= ' ! " ) % λ = 0, 0389 λ = 0, 6181 6 ×16 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
38=
;
@!3
@!
@!2
@!6
@!?
@[email protected]
@!7
n = 4 ) $ λopt = ϕ−1 µ = 1 : λmax =
√
2−1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
7 $ n = 4 ! ! ! ! ! ! ! ! ! ! ! ! !
> θ2 ! ! ! !
(ABC) . B ) λoptB = 0.5
6 ' ! ! ! !
! ! ! ! ! ! ! ! !
(a, c) (b) ! !
38
333
! ! ! ! ! !
33
! ! ! ! ! !
336
! ! ! ! ! !
33?
! ! ! ! ! !
[email protected]
! ! ! ! ! !
337
! ! ! ! ! !
33=
3!2
? n ! ! ! ! ! !
( >@ ! ! !
( % * 6!3
( 6 3!3
3!
33
! !
23
! !
26
! !
2?
! ! ! ! ! ! ! ! ! ! ! ! !
=6
.9A /A. 9"A$G
3
+ # ' * + ! 0 ' + +
+ !!! +
(- - !
H # ' + ( ( + !!! + I B > ((!!!
. ' + ) + ( # + + ' + ( + ( !!! * '
! + ' ( C + ( + ' !
J ) *
+ ) K3;L B K32L 1 ' ( M K6L!
) (( + ( # H
+ # 1 +! # ' ) ( !
+ 1 ' !
A B ' ) ) 32
- K37L 1+ ! + +
) + ! ( + (
N + ( (( ) # + B ' + ( !
D 1 + ( B # + ! # ' ) ( ! ) ( 6 @ ( +! D - ) ( + ( - +
+ '# ( 6 - 1 ' + + + ( ? @! # # '
4+ 3;[email protected] K23L!
36
3?
[email protected]
D + ) # ' ! > ) # ' * # + ( ) ( ) : # ! ' + H + # ) ) !
( ) #
1 '# 1 ( # B )
( !! D + ) * ) !
/ ( + !
/ ( + ( B + + ! # ) + ! D 1 + ( !
D 1 ) ( +
+ 37
+ ( # ) )! / + + ( ( + ( ) !
3=
/ ( +
+ (!
D , 3!3 1 + + (- Rd B + # + + # !
D 3! + '# + H ) !
D 1 3!2 + > + ( +!
) + ( * + #, 1 + ! D + 1 !
D 1 3!6 + + + ! # ( ) : + ( ! D 1 H + B (
!
3;
O094A 3! <D9AG9A
0+0+0 7 + + + + + + + + + + + + + + + + ,0
0+0+, + + + + + + + + + + + + + + + + + + ,0
0+,+0 A + + + + + + + + + + + + + + + + + + + + + + + + ,,
0+,+, + + + + + + + ,
0++0 + +
0++, - + + + + + + + + + + + + +
+ + + + + + + + + + + +
0++ B + + + + + + + + + + + + + + + + + + + +
0++5 ( % + + + + + +
> + + + + + + + + + + + + + + + +
: + + + + + + + + + + + + + + + + +
- + + + + + + + + + + + + + + + + + + + + +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
0+5+0 - + + + + + + + + + + + + + + + + + +
R2 P2 + + + + + +
+
0+5+, 2. * + + + + + + + + + + + + + + +
0+5+ ( + +
+ + + + + + + + + + + + + + + + +
-% + + + + + + + + + + + + +
8
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
,5
,5
,'
,6
,4
,4
,4
,9
,C
!
1
1
,
'
O094A 3! <D9AG9A
. + # 1 ' + + + (- 1
d! D + (- 1 K? ! 227L!
( ) . H n (- Rd ! H -
' !
- # d
+ H A(H)!
< ) + +
d (- H d + 1 (- ! / + !
/ )
1 R2 >
( ) 5 1 n D = {D1 , . . . , Dn }
+ A(D) R2 8 3 ( * -+ !
/ Dn n A(Dn ) + 1 3!2!3! D An
+ 1 !
D + A(Dn ) +
An !
3
O094A 3! <D9AG9A
< 1 * # +
*
-+ #
# *
-+ # ! * ( + (- Rd !
) P ) + '# * ! / Q R !
+ + 1 +
) (- ) P! ( H # H '#!
+ '# !
!"
. + # 2!3 '#
P * 1 R3 ! * () R3 > () + + O ! R3 * P2 !
2
>
& *
3! '# P2 !
! '# P2 !
2! / # >
'# P2 H K?
! 3?;L!
!
O094A 3! <D9AG9A
! !"
'# # # >
3! . 1!
) ! '# - > Q 1R Q SR!
2! + Q 1R (+ ) '# !
% 0+0 # + ( $ C $ 6 4 $ 5+
A # a4 a6 a3 + ( a7 a9 a5 +
(. f2 a4 , a2 , a7 f7 a6 , a9 f2 a2, a3 , a5 +
- f2 ! $ % "+ / . f2 # s3 a5 f2 $ . ! $ % " f2 $ a5 + - , 7 $ % P2+
f7
a9
f2
a6
a5
s3
f6
f4
a5
f1
f3
s3
a4
a8
s1
s2
a3
a1
f3
f1
a2
f1
a4
f2
a6
f4
f5
a1
a3
a7
3!3 T s1
2
s2
a1
f3
a3
n = 3
a2
f2
a5
O094A 3! <D9AG9A
#
( ! ! ! !
c, c |d − d | = 1 ) / + (- A(H) d, d
# ) !
. d = d − 1 c ≺ c [email protected]! / * d+1
cd (cd+1
)1im c ≺ (cd+1
1 , . . . , cm )!
i
/ + #!
/ * *
1 + ( >
( ) + ( + A(H) >
T U ( A(H)
T ( - A(H)!
+ ( + U
Q+ R # 1+ 3!!
1 + ( ! /
+ ( *
) ! + ( ' *
* 1+ 3!! + !
> .
) + '# + ( +) 1 > U 1 + ( ++ + ! '# *
# ! + ( + 6 # 1+ 3! 3!2!
#
!
$ 0 + # + ( G 6
O094A 3! <D9AG9A
f7
a9
s1
a6
s3
s3
f6
f4
a1
a5
s2
a2
a3
a4
f1
f2
f3
a5
a6
a7
a8
f5
f6
f7
a9
a8
f5
s1
a1
s2
a3
a2
f1
f3
f2
a4
3! T n = 3
s1
f2
a5
f4
a7
s2
s3
a3
f1
f3
s3
a4
a1
a2
a4
a3
a5
a6
a6
f4
s1
a1
a2
s2
a1
f3
f1
f2
a3
f1
f2
f3
f4
a5
3!2 T An Dn
An = A(Dn )!
) 1 Dn + ! D * G An + !
' +
( ) / + *
* * !
/ + * * !
! " # & , ' -)
?
O094A 3! <D9AG9A
$ % a a & s ! a a '
& # ! a # ! a (
) 1
1
2
2
2
1
/ # s $ a1 a2 a3 a4 # $ s ) s ≺ (a1 , a2 , a3 , a4 ) %+ 0+5+
A i = 3, 4 # # fi,1, fi,2 fi,1 $ a1 ai fi,2
$ a2 ai ) (a1 , ai) ≺ fi,1 (a2 , ai) ≺ fi,2+
a3 a4 +
s1
f3,1
a3
f3,2
s1
a1
a1
f4,1
a4
a2
a3
a4
a2
f4,2
f4,1
f4,2
f3,1
f3,2
3!6 T /)
+ ( 1 *
! 1 # C + ( + ( + *
6!
$ + ( ) Q(( R s * a1 * a2 a1 s! + ( + ( B
(( C > 3 + ( @
U !
. # (P * + ( +V + ( >
@
O094A 3! <D9AG9A
! < n(n − 1) # + ( Q(( R n > * (
+ + ( !
##
%&!
( $) /
+ (- + ( ( + ( ' !
> + ( ' ! A +
'# * B !
? 1+ 3!?!
> ) * + > H + * I 1+! 3!!
#'
(
) &!
D ( ( + ( 1 ( # !
/0 / + ' K3;L
'# "! W # * - d ! 2;6 + + ( ' # * - !
7
O094A 3! <D9AG9A
4
4
3
3
3
3
3
3
5
4
5
4
3
3
3
3
4
(b)
(a)
5
4
3
3
4
3
3
4
4
4
3
3
(c)
(d)
3!? T !" # ! $ % " 1 < K32 ! 33L 1 # > di + p 1 vi (p) = +1 p ∈ d+
i = 0 −
p ∈ di = −1 p ∈ di p di p 1 u(p) = (v1 (p), . . . , vn (p))!
+ 1 + 1+ [email protected]
k ! ' + S !
((
+ 1 ' k ! D > =
O094A 3! <D9AG9A
5
+++++
−0
++
4
+
+++00
+++−−
3
−−−−−
2
1
[email protected] T & ' + '# + ! / !
A 1 ) + + + 1+ ! D ' # + + !
> # # ( + ( ! 1 # O! A !
2 / [email protected] " + 1 ! $
d + 1 ) !
/ + + # # + ( (
( Q(R Q R + (! 0 + 1+ 3! (s2 , a3 , f3 )!
;
O094A 3! <D9AG9A
+ ( X ! 0 !
+ >
( + n + B * ! + W K3;L ' (
( :
KL K2L + ( (( ( !
'
* "!
0 ) + + n (- d '# k cdk (n) +! < K32L K3; ! 2;2L '# >
cdk (n)
=
k
k−i
d−i
d−i
n
=
d−k
n
i=0
cdk (n)
=
d−k
n
k
in+k−d
i=0
k
in+k−d−1
'#
i=0
(
. + cdk (n) O(nd )
k 8 d # + !
+ + + # + K3; ! 2;2L! D !
34 R2 P2
/ + n ( * # ! / * + + + !
>
28
O094A 3! <D9AG9A
=
*
#
cd0 (n)
= cd1 (n)
= cd2 (n)
A 0 '#
n(n−1)
2
n(n−1)
2
n(n − 2)
2n
n2
n(n−3)
+1
2
2n
n(n+1)
+1
2
n(n − 1)
n(n−1)
2
+1
3!3 T ? n < O(n2 ) + O(n) ! + + + (- Rd > O(nd ) O(nd−1 )!
) + = # +
2 + - . +
D 7 ) !$ % " # ! " + 8 +
- A(D) n − 1 D ne +
D (n − 1) , n − 2
+
= ) â(n) = 2n ā(n) = n(n − 2)+
A )
f¯(n) = f¯(n − 1) + (n − 2)
fˆ(n) = fˆ(n − 1) + 2
- # +
23
O094A 3! <D9AG9A
34 4 !
/ + * +
> 3 * ) !
/ '# ) ! # - # + +!
* n + (
, m $ n $ ! n , . . . , n $ ! % n = n + n + · · · + n ( $ & )
0
1
m
0
1
m
1 m
(Σ
ni nj + n0 (n − n0 )) + m
2 i=j=1
a = n(n − 1) − Σm
= n0 (n − 1) + Σm
i=1 ni (ni − 2)
i=1 ni (n − ni + 1)
1
1
1
= 1 − m + (n0 (n − 1) + Σm
f = 1 + n(n − 1) − Σm
i=1 ni (ni − 3) − m
i=1 ni (n + 2 − ni ))
2
2
2
s =
3!7 T ( $ ) % ) . s !% " $ +
8 %+ 0+4 $ ni 2 < ni < n % + - % # ni + 2 +
A i m % ni(ni − 2) 1 + ni (ni − 3)/2 % E $ # # +
2
O094A 3! <D9AG9A
'
+
,
- ( ) : +
+ (! B + ( 2!2!3! A # K?L >
( ) . A(H) d+ H n (- H (- H!
k 0 k d A(H) H H + A(H)!
- & ) . - R O(n )(
d
A(H)
d−1
n %/ / +1 + '#
n : O(n) * O(n)
# # !
D3
D2
c7
D4
a8
a9
s3
c6
c3
a5
a7
c5
s2
a1
s1
c1
a3
a2
c4
c2
3!= T * D4 D1
a4
a6
A(D1 , D2 , D3 )+
> ( ) # ' )!
'#
( $
. / K3;L K8L "! W + ) # ! 2;6 >
22
O094A 3! <D9AG9A
n=
Y '!
Y '!
Y ! !
Y ! 2
3
3
3
3
6
3
3
3
?
3
6
@
7
@
6
[email protected]
62
7;
7
33
; E
[email protected]? E
3! T ( >@
5 4 0 D W + !
/ + ) - - > +
!
/ + (
B !
1 ' !
% / 3! ; [email protected]? C Z W! 1 + ! A B (( - 1+ '# >
n=
2 6
Y ! 3 3
Y '! 3 3
?
7
3
@
7;
6
7
[email protected]?
33
=
[=7888
[323
+ ( + ( + + ( ) + ( ! A + + \\ + \ \! + B ( * 38 !
$ A Z W + + !
K37 ( ?L
n 8 +
26
O094A 3! <D9AG9A
+ ! Z W
7 ' !
/ + ? 7 B @ 1 ! 1+ 3!; 1 1 ! D 7 + ? - ( ! 1+ 3!; ( +(!
(4 (
/ KL K2L (( :
) > * ) ' n = 10 !
0
1+ ) n ! # ' + n 1+ n !
>
+ 1 ( #) /
1+ * n !
) 3!2 + # '# 1+ + ( # !
n=
1+! '!
1+! !
6
3
?
3
2
@
6
[email protected]
7
33
32?
=
32?
223?
;
38
62=3
23 336
3?= =37 36 28; ?67
3!2 T ( % *
D # # W + # (( : ( !
2?
O094A 3! <D9AG9A
4
3
3
3
4
4
5
4
3
3
3
3
5
4
3
3
4
3
4
3
4
4
3
3
3
3
4
4
3
3
5
4
3
3
3
3
3!; T # ' [email protected]
( > 1 + (+ +! 1 # H + H # !
H + + ! A + Q R!
) 1 + + 1 (
1 # ! D + !
/ ) + !
27
O094A ! .<9<0A 0A49$4"9<D .9"95
"
!
,+0+0 A + + + + + + + + + + + + + + + + + + + + + + + C
,+0+, = + + + + + + + + + + + + + + + + + + + + + + + + + 51
# ,+,+0 8 + + + + + + + + + + + +
,+,+, 8 + + + + + + + + + + +
,+,+ A + + + + + + + +
8 ( # (T , R) +
8 + + + + + + + + + +
$
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
51
5,
55
5'
56
54
%
,++0 A + + + + + + + + + + + + + + + + + 59
,++, - + + + + + + + + + + + + + + + + + + + 5C
F + + + + + + + + + + + + + + + + + + + + + 5C
2=
O094A ! .<9<0A 0A49$4"9<D .9"95
1 ( 3 # + ! 0 + # + 1 Q + R Q# R +! D !
0 # ( ( * 1 K6L!
+ )
( !
A1 1 #, # + ) !
D ) ( > Di (ai , bi ) N ai x + bi y + 1 = 0 Di !
Pij = Di ∩ Dj 1
xij
bi − bj
Pij =
=
yij
ai bj − aj bi aj − ai
> + O ! ) +* ( O (+!
. + ) ( # '
# ( +) ax+by +cz = 0 # +
'#! / * # y = ax+b A K32L! / () K;L ] 0( + Q R ai x+bi y −ci = 0, a2i +b2i = 1, ci > 0
( !
2;
O094A ! .<9<0A 0A49$4"9<D .9"95
. + >
Pij
ak xij + bk yij + 1 = ak
) si,j,k
Dk bi − bj
aj − ai
+ bk
+1
ai bj − aj bi
ai bj − aj bi
+ ai aj ak = ak (bi − bj ) + bk (aj − ai ) + (ai bj − aj bi ) = bi bj bk 1 1 1 > #, + Pij , Pjk , Pki!
! / ) # n D = (Di (ai , bi ))1in ) # + D 0 = (Di0 (a0i , b0i ))i D 1 = (Di1 (a1i , b1i ))i
1 i n! ( ) !
$
D , !
$
$
( ) 4 $
$ ) 1 0
0 0
0 0
∆ = (a1 , b1 , . . . , an , bn ) ∆1 =
(a11 , b11 , . . . , a1n , b1n ) # ! D ' (- () 1 !
∆ = (a1 , b1 , a2 , b2 , . . . , an , bn ) : [0, 1] → R2n
0
a
ai
(0) = 0i ,
∀ i,
bi
bi
68
1
ai
a
(1) = 1i
bi
bi
O094A ! .<9<0A 0A49$4"9<D .9"95
+ D ai (t) aj (t) ak (t)
bi (t) bj (t) bk (t) = 0 ai (t) aj (t) = 0
bi (t) bj (t) 1
1
1 ∀ (i, j, k) ∈ 1, n, ∀ t ∈ [0, 1],
+ + !
> ) (+ !
+ ) - !
>
( ax + by + 1 = 0 + ! A B # ∆ > ai bi 1!
>
(- () + ∆ R2n ! +1 # * 1+ + !
(- () 1 ' + !
( %) 4
(ai , bi )i,1in 1 R2n D ΓD !
> Γ
D
C ) ( )!
. Γ D = (D (a , b ))
R (
5 )
D
2n
i
) % 2n
R−
∗ % R +
( i
R+
∗
i
) 4 $ $ < + B !
1
D )
63
1in
O094A ! .<9<0A 0A49$4"9<D .9"95
> 1 ( +
+ Q ) R ! D # + + # !
< + + + 1 + + ! / * H * + !
&
+ ! 0 + + * 1 + ) !
# >
( ) D 1 Dk (ak , bk ) Dk (ak , bk ) # a, b : [0, 1] −→ R a
ak
(0) =
,
bk
b
∀ t ∈ [0, 1],
( a
a
(1) = k
bk
b
D ai aj a(t)
ai a(t)
= 0
∀ (i, j), (1 i, j n, i = j = k) : bi bj b(t) =
0 bi b(t) 1 1
1
) (a(t), b(t)) 1 Dk !
1 38!
( ) '
< & )
(
1
D ) B !
. $ 6
O094A ! .<9<0A 0A49$4"9<D .9"95
) 8 +
+ 8 G ∆ +
/ ∆ ∈ C([0, 1], R2n ) +
∆ ΓD .
+ A ∆(t) ∆ t ∈ [0, 1] # R2n Π1in [ai(t), ai(t)] × [bi(t), bi(t)]+ - ∆ ΓD +
O
∆0
l+1
O
ΓD
ON
l
O
1
∆1
!3 T ∆ Ol % ,
= ∆ [0, 1] + = # R2n % ∆+
? l
O = (Πni=1 [ali , ali ] × [bli , bi ])l ,
l ∈ 1, N % ,+0+
8 G Ol ∆ + ) 3 ! " . Ol +
(a01 , b01 , a02 , b02 , . . . , a0n , b0n ) −→ (a11 , b11 , a02 , b02 , . . . , a0n , b0n ) −→ (a11 , b11 , a12 , b12 , a03 , b03 , . . . , a0n , b0n ) −→ . . .
. . . −→ (a11 , b11 , . . . , a1n−1 , b1n−1 , a0n , b0n ) −→ (a11 , b11 , . . . , a1n−1 , b1n−1 , a1n , b1n )
n Ol
Γ 3 Di(ai , bi)+
∆ Ol $ Ol+1 H + D % ∆ n × N 3 Γ+
62
O094A ! .<9<0A 0A49$4"9<D .9"95
> + ! A # !
. Γ D 1 R (
& $)
Dk
2
) a a(0)
i
s̄i = sgn = ±1
bi b(0) a u
i
¯ i : R2 −→ R, (u, v) −→ ∆
bi v / Γ = Γ1 ∩ Γ2
%+ ,+, Γ1 =
a a a(0)
i j
s̄¯ij = sgn bi bj b(0) = ±1 1 1
1 a a u
i
j
¯ : R2 −→ R, (u, v) −→ b b v ∆
ij
i
j
1 1 1
i
Γ2 =
k
¯ −1 (s̄i R+ )
∆
∗
i
,+0
¯ −1 (s̄¯ R+ )
∆
i ∗
ij
,+,
ij
. Dk (u, v) . # ) I R2 # + - # # !" Dk + D O # Γ1+
Γ2 . Dk (u, v) D+ - + Γ2 +
Γ1
#
/ ) !
) +
# D1 D2 D2 # D1 ! 0 + # ' !
( ) < 66
O094A ! .<9<0A 0A49$4"9<D .9"95
b
b
Di
Dk
b
Γ2
Γ1
Γ
Dk
a
a
O
Dk
O
a
O
Dj
! T - Dk
. 1 2( . (
#( . 1 A(D ) $ D 0 3 $ $ A (
) & )
n
n
n
+
* ' . $ 4 5( . (
) & #)
G $ % + & +
A $ J04 + 011K ) . L + ( R2n . ! " #+ 2 .
> 05 # $ 01 +
- # # # 3 $ +
6?
O094A ! .<9<0A 0A49$4"9<D .9"95
D ' 1 + ! D # + + !
* (T , R)
6 D (a , b ) 4T R5 0 & T D 1 ! & R D θ O
7 % 8 % A(D \ D )(
) & )
i
i
i
i
i
i
$ ' ∆ = (a, b)
$ R2 R2n ∆ Di0 $ Di1 + ∆ (a, b) ΓD +
D# 3 Di(ai , bi )
. (a, b) )
Di : ai x + biy + 1 = 0 + . $ ai /bi Di0 $ Di1 %+ ,+ Di0 ) Di . +
b
b
D
0
D
D
0
1
D1
a
a
O
O
!2 T & .
A θ )
$ (ai , bi)+ (a, b)
Di O Di0+ &
Di0 $ Di1 . %+ ,+ +
A $ . ) O+
[email protected]
O094A ! .<9<0A 0A49$4"9<D .9"95
- Im∆ ΓD ΓD + ( # % O = (Oi ), i N ∆+
b
O2
∆0
O1
ΓD
∆1
a
!6 T ( $ 8 G Oi ∆ T R ΓD +
D % ∆ N (T , R) (R, T )+
) 1 (T , R)(
) %)
8 G (T , R)+
> <
V( +) (T , R) N ( R + Di !
+ # # ( !
D , ) 1 1+ ( 1 ! 1
67
O094A ! .<9<0A 0A49$4"9<D .9"95
!3! + )
) > (
! Q- R 1+ 1 K3=L!
/
" J !3 ) + + > + Di (ai , bi ) + # E 0 #, * +
E
#
$ D + S ( )!
6 $) D D̃i (ãi , b̃i ) ( ãi = ai + εi
∀ i, |εi| ε
b̃i = bi + ηi
∀ i, |ηi | ε
εi , ηi ) ai , bi ε ∈ R+ S - ) ai , bi !
D i, j, k n Mij = max(|ai |, |bi |, |aj |, |bj |)
Mijk = max(|ai |, |bi |, |aj |, |bj |, |ak |, |bk |) + M = max(|ai |, |bi|)
1 i n!
i, j >
δij = ãi b̃j − ai bj = (ai + εi )(bj + ηj ) − ai bj
= ai ηj + bj εi + εiηj
|δij | ε2 + 2ε max(|ai |, |bj |)
< |δij | = |ãi b̃j − ai bj | ε2 + 2εMij
6=
!2
O094A ! .<9<0A 0A49$4"9<D .9"95
#
* $
V ' ε
* >
6 ) 0 i, j, k ∈ [1, n]
+ !3!3 >
si,j,k
7 & )
ai aj
= bi bj
1 1
a
si,j = i
bi
ãj ãk b̃j b̃k 1 1
ãj b̃j 29 2: R
Eo
Enp
1
2
0, Mijk
=
+ |sijk | − Mijk
6
i,j,k
1
0, Mij2 + |sij | − Mij
=
2
i,j
* ε ∈ E ∩ E A(D )(
) o
ãi
s̃i,j,k = b̃i
1
ã
s̃i,j = i
b̃i
ak bk 1
aj bj np
A(D̃i)
! i
A # ) . +
& - s̃ijk + =
(Pij , Pik , Pjk )
sijk = ak bi − ak bj + aj bk − ai bk + ai bj − aj bi
(M
s̃ijk − sijk = (ãk b̃i − ak bi ) − (ãk b̃j − ak bj ) + (ãj b̃k − aj bk ) − (ãi b̃k − ai bk )
+ (ãi b̃j − ai bj ) − (ãj b̃i − aj bi )
= δki − δkj + δjk − δik + δij − δji
6;
O094A ! .<9<0A 0A49$4"9<D .9"95
D % . ,+
,+5
|s̃ijk − sijk | 6ε2 + 12εMijk
,+5 G ) |sijk | > 6ε2 + 12εMijk s̃ijk + 8 G I
ε )
f (ε) = 6ε2 + 12εMijk − |sijk | < 0
,+'
2 + 6|s | > 0 #
∆ijk = 36Mijk
ijk
ε ∈]ε1, ε2 [ ε1 =
ε2 =
−6Mijk − ∆ijk
6
2 + 1 |s | − M
= − Mijk
ijk
ijk < 0
6
2 + 1 |s | − M
Mijk
ijk
ijk > 0
6
= ε ε2 ,+' )
ε ∈ Eo,ijk = 0,
2 + 1 |s | − M
Mijk
ijk
ijk
6
D ' i, j, k M G ) ε ∈ Eo = i,j,k Eo,ijk +
& ( H # Di , Dj s̃ij = ãi b̃j − ãj b̃i + =
s̃ij − sij = ãi b̃j − ãj b̃i − ai bj + aj bi
= δij − δji
|s̃ij − sij | 2ε2 + 4εMij
8 G $ |sij | > 2ε2 + 4εMij s̃ij $ ,+6
f (ε) = 2ε2 + 4εMij − |sij | < 0
2 + 2|s | > 0 ε ∆ij = 4Mijk
ij
ε1 = −
Mij2
1
+ |sij | − Mij < 0
2
ε2 =
1
Mij2 + |sij | − Mij > 0
2
$ ε $ )
ε ∈ Enp,ij = 0,
1
Mij2 + |sij | − Mij
2
?8
O094A ! .<9<0A 0A49$4"9<D .9"95
- $ ε ∈ Enp = i,j Enp,ij +
> 0 +!
- ε
?3
Di , Dj O094A ! .<9<0A 0A49$4"9<D .9"95
?
!
"# ( +
!
D , + ' + + '# 1 # !
D !
D + ( ! + ( ! D + ( B + !
D 1 + ( H * ( ! D - - + C ( + ( + + ( ) !
?2
O094A 2! <D.94$9<D A9 05AD99<D
( ) **
&'+ *%
& ? + + + + + + + + + + + + + + + + + + + + + + +
- + + + + + + + + + + + + + + + + + + + + + + + +
+0+0 A $ % + + + + + + + + + + + + + +
+0+, ( ) % + + + + + + + + + + + + + + + + + + + + + + + + +
( + + + + + + + + + + + +
( + + + + + + + +
+ + + + + + + + + + + + + + + + + + + +
+,+0 - + + + + + + + +
+,+, / ) (% + + + + + + + + + + + +
8 + + + + + + + + + +
+,+ = D + + + + + + + +
, ++
++
++
++
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
++0 - + + + + + + + + +
+ + + + + + + +
7 + + + + + + + + + + + + + + + + + + +
++, - + +
+
7 + + + + + + + + + + + + + + + + + + +
> + + + + + + +
& +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ + + ''
+ + + '6
+ + + '6
+ + + '4
+ + + '4
+ + + '4
+ + + '9
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
'9
'C
'C
61
61
-
60
60
6,
6,
65
6'
6'
-.
+5+0 -E + + + + + + + + + + + + + + + + + + + + + + + 64
+5+, = . # + + + + + + + + + + + + 64
+5+ A + + + + + + + + + + + + + + + + + + + + + + + + 6C
?6
O094A 2! <D.94$9<D A9 05AD99<D
# $ / S '# S
# + B! D 1 '#
B + !
6 0 M # ' R
M + ' '# P2 M ' R2 !
'# P2 # 1 R3 R3 R > xRy λ ∈ R∗ , λx = y ! D 1
P2 ' R3 P2 R2 !
D ( +) > (α, β, γ) M P2 * M R3 !
−
→ −
−
→ →
) (Ω, i , j , k ) / ( R3 3
Ω
Hc
z=−1
M
Ο
D
P
2!3 T ??
R3
+ z = −1
O094A 2! <D.94$9<D A9 05AD99<D
H ' + 1 (f, g, h) ∈ R3 H : f x + gy + hz + 1 = 0!
' M P2 M R3 M H R2 >
R3 −→
P2 −→ H
M(α, β, γ) −→ M(α, β, γ) −→ M = (OM) ∩ H
. H Hc R3
1 z = −1 (fc = 0, gc = 0, hc = 1)!
( +) 1 >
T M(α, β, γ) P2 (OM) R3 −−→
(α, β, γ) OM!
T D(a, b, c) P2 R3 (a, b, c) !
N
M(α, β, γ) ∈ D(a, b, c) ⇐⇒ αa + βb + γc = 0
T D1 (a1 , b1 , c1 ) D2 (a2 , b2 , c2 ) P2 M(α, β, γ)       

α
a1
a2
b1 c2 − b2 c1
β  =  b1  ∧  b2  = a2 c1 − a1 c2 
γ
c1
c2
a1 b2 − a2 b1
T D(a, b, c) >
M1 (α1 , β1 , γ1 ) M2 (α2 , β2 , γ2 )
      

a
α2
β1 γ2 − β2 γ1
α1
 b  =  β1  ∧ β2  =  α2 γ1 − α1 γ2 
γ1
γ2
α1 β2 − α2 β1
c
'# R!
#
H ' > Q )
. )
D ( 3 ) Q 1R (( '# I '# [email protected]
O094A 2! <D.94$9<D A9 05AD99<D
+ !
/ ( Q 1R R2 H O ) H ( : z = 0 H = Hc P2 R3 H + ' Q 1R!
+ + 1 C ( 1 (+ C
' H 1 ) '# !
#
( / ! ) A + 1 '#! / Pn # ' d ' n−d−1 I P2 # ! / I > P2 p ∈ D D̂ ∈ p̂ !
!
( +) '# 1 #, > p 1
(α, β, γ) D (a, b, c) 1
> ax + by + cz = 0!
B * > p(α, β, γ) → p̂(α, β, γ) x.α + y.β + z.γ = 0
1 ( Di ( !
/ '# ( +)
# ! 0 ( +)
' hx + ky + lz + m = 0! < ( + ( ' ((
Dualp : D(R2 ) −→ R2∗ , ax + by + 1 = 0 −→ (a, b)
?7
O094A 2! <D.94$9<D A9 05AD99<D
& P (a, b)
, !
4 -)
d(D, O) = √
) N=
a
b
(M )
* D(ax + by + 1 = 0) 1
1
=
2
d(P, O)
+b
a2
xH
$ D+ / H = y O D+ H ∈ λN ∩D
H
7 . ) xH = λa yH = λb axH + byH + 1 = 0 λ(a2 + b2) = −1+
−−→
OH = |λ| N =
√
1
a2 + b2
=√
2
2
2
a +b
a + b2
3 D 1 ! K3L Dual2 : D(R2 ) −→ R2∗ ax+
a
b
by = 1 −→ ( a2 +b
2 , a2 +b2 )
) B ( ( ! )
!
%& ' 9 H + + ( + # + # + ( +
' !
D H + !
#
*! D ( '#
( ' H ! 0 ?=
O094A 2! <D.94$9<D A9 05AD99<D
+ + ' + ' + ' ' '# ! D ++ ^^
' ! # '# ' # 2!3!
#
! / $ 0 # ( ( ( ( ! < * /A
K38L + K? @ 7L [email protected]!
- ' + ( + + # + !
( $ D * ! 1+ 2! * a1 s1 s2 > b1 ( s1 Q R s2 b5 ( s2 s1 ! b1 b5 Q R '!
b5
b2
s2
b1
b3
a1
s1
b4
2! T / 1 + 1 + Q R! ( 1 * # I '#
1 ( * >
T ( ! !
b2 = succ(b1 )
?;
O094A 2! <D.94$9<D A9 05AD99<D
T b4 = prec(b1 )
T * * " b5 = swap(b1 )
T ( * + * b3 = trans(b1 )!
D 1 * " + ! D ' 1 + +
+ !
> +
+ 6 ( * > H + !
# + * + '# N *
' + Q 1R!
# # ( ^^ "
!
##
0
A + ' + > * ' * ! H ! D + ( ) + 1 ( !
@8
O094A 2! <D.94$9<D A9 05AD99<D
% ( / ( D n
# ai x + bi y + 1 = 0 (( + A(D) + ( 1!
A B + ( B ( + ( 1 !
##
* ! !
+ ( +
( : !
> + n ' (n + 1)e ! . : ) ( ) * 3!6! O(n) + ( ' : O(n)! + ( K32 ( ! 7L ! A (
>
3 4 0 2
# $% &'
# ( )
* + , * ) &'% &'-
# . $/ $% %
) ' $ (
&' &'
0 &' '
1 @3
O094A 2! <D.94$9<D A9 05AD99<D
# ) ,
&' (
&'
2 ) $ 3$ ) # )
(
&' 45 $$ $$ 2 $ 1 2 # + & ,
!
+
&'
&'
&'
,
,
1 1
3 8
+ ( 1+ 2!2
2 >
: ! + 2
6 !
+ ( C ( K32L ##
* ! $
O(n2 ) !
D + ( + B ) > B Q+ R #, I B , +!
0 - >
@
O094A 2! <D.94$9<D A9 05AD99<D
f7
a9
s3
f3
s1
a8
s2
s3
f6
a1
a5
a2
a3
a4
f1
f2
f3
a5
a6
a7
a8
f5
f6
f7
a9
a7
f5
s2
s1
a1
a4
a3
f1
f4
a2
c7
a9
s1
a8
s3
c3
f4
a6
f2
s2
c6
a1
a5
a2
a3
a4
c1
c2
c3
s3
a5
a6
a7
a8
a9
a7
c5
s1
a1
s2
a4
a3
c1
c4
c2
a2
a13
a9
c11
a16
a4 -> a14
a6 -> a15
a8 -> a16
a8
a12
s3
c3
c10
c6
a5
c6
c7
a6
s6
c7
c5
c4
s1
a1
a7
s2
c2 -> c8
c4 -> c9
c6 -> c10
c7 -> c11
a2
a3
a4
c1
c2
c3
s3
a5
s4
a6
a7
a8
c5
c6
c7
a9
a10
s5
a11
s6
a12
a13
a14
a15
a16
c5
s1
a1
a3
c1
a2
c2
s2
a4 s4 a14
c4 a11
a6
c9
s5
c4
c8
a15
a10 c8
2!2 T - ) 0,
@2
c9
c10
c11
O094A 2! <D.94$9<D A9 05AD99<D
d + k + 0 k d !
( #) < 8 3 * # * !
3 4 0 * ] # $% + ( >
&'
# ( )
* + , * # ) 4 6-
$% $% %
) ' $ (
&' &'
1 1 # 7 $% 72 &'
1 # ) % $% ) 1 4 6- 4 6-
&'
# ) - 4 6-
#4 6-
) 8 ) 8 1 1
@6
#4 #4%
O094A 2! <D.94$9<D A9 05AD99<D
3 8
< 8 ! 0 ) Q +R ( (
!
C O(n2 )!
((
< 3 1 * ! + ( ( +!
*
1 # ) !
D - C O(n log n)! 0 + n O(n2 log n)!
;
A1
# * * ! ( # > +(! A (
* ( > # +( ! A 1 ( * # !
( + *! <
B O(n2) C !
A 1 + ( O(n2 log n) + ( n × (n log n)! !
/ D + + ( + 2 ! " C + > + 8 O(n3 ) 3 O(n3 log n)! ( O(n2 ) 8
3 (+ ! 2 >
2 # ! A 1 # ! D '#!
@?
O094A 2! <D.94$9<D A9 05AD99<D
D2
D3
s1
s2
s3
s3
s1
D1 : (s1, s2)
D2 : (s2, s3)
D3 : (s2,s3)
D1
s2
D3
D2
a9
a6
s1
s2
s3
s3
a5
a8
a1
s1
a1
s2
a3
a2
a2
a3
a5
a4
D1
a6
a7
a8
a9
1-squelette
a7
a4
D2
D3
c6
a9
s3
c1
s1
a6
s3
c5
a1
a5
s2
a2
a3
a4
c1
c2
c3
a5
a6
a7
a8
c5
c6
c7
a8
c7
s1
a1
s2
a3
a2
c2
D1
c4
a4
c3
c4
a7
2!6 T - , ) 1 0 ,
@@
a9
O094A 2! <D.94$9<D A9 05AD99<D
#'
% * 1
!!
1+ 2!? + ( + # ! 0 + # 1+ I + ( ! # 0 0 22 O:! D + ( (- 4! ) : - !
A + ( ( O(n2 log n) ) +) H + ( O(n2 )! A + ( 2
2
O(n log n) O(n )! < 38_ 3_ ' 3888 ! A 1 # C !
;
/ + + ( # + ( QR !
#'
!!, 2
" C ' H + (
! A *
- ) + + ( + + ! A B + # + + V( B ! / + ( ( + !
@7
O094A 2! <D.94$9<D A9 05AD99<D
6
total
5
4
3
2
1
0
0
200
400
600
800
1000
6
init
+calcul
+tri
+squel
+faces
5
4
3
2
1
0
0
200
400
600
800
2!? T 2 # 1000
/ # H + ( + ( > *
+
n2 + ( #
# + ( Q R - ) ( @=
O094A 2! <D.94$9<D A9 05AD99<D
!
A B + ( B ( : O(n) ' ( !
# #
) O(n) * : Q R O(n2 ) ! + ( Q R # )! A B
X * * ) > 3 * ! ) # Q R
! A O(n2 log n) B
# n ( + n − 1!
H + ( ( [email protected] Z 0 # X
) ) ' ! + + ' #!
) + 38888 + ( > + ( Q R + (
Q R!
#'#
$ ) + + ( )
# ' n ! A B Q R ' ! * ) (( # 1 # 1 ! D # !
# + ( !
@;
O094A 2! <D.94$9<D A9 05AD99<D
A ( + ( P *
H > * ( + !
78
$ % # 73
7
) Q R 1 + ! / ' S + (
B +
! ) ' 1 + * 1
1 Q R # + # + + + + !
K37 ( ! ?L + ! ( + ! / + 1 + ' ' + ! # + ( : #, ( -+ B
* + ( 1+!
[email protected]!
/ ( ( + -+ ( K=L! $
-+ -+ - S + + S ! &+ [email protected] -+ (CBDE) + 6 ! < # -+ + +!
72
3
2
C
3
2
C
4
1
4
1
B
B
E
1
E
4
A
D
F
A
D
F
2
3
4
2
1
3
4
1
3
1
3
B
C
D
2
3
A
2
4
4
3
2
D
C
F
E
F
E
2
4
B
A
1
1
[email protected] T (# 3
/ + 1 Q R +
* K3L ! 1 * * ) ) !
< +
+
K2?L + (- ' 2/ () D . K26L ( K27L + !
</
);
!
0 ( +
! ) + !
A + '# ' # ) ! ' ( 6!
76
A + # ! D 1 ) + (( + ) + # P! ( + ( # ' ( ?!
A1 ( @ - ) > +
2 ? )
+ + !!!
7?
[email protected]
&
$ ' ( / ( + '#! . )+ + Q ' R ( ) # ( > ' #, Q 1R # ' Q R 1 + !
Q R ( 1 ) H P + '# - # + ) !!! # ! 9 # )+ ( # ( @ + ( 6 + '# (
( !
77
O094A 6! /$ 04<%A9& J A$/AD
/ '+ /
0
."
."
5+,+0 ( * + + + + + + + + + + + + + + +
5+,+, . + + + + + + + + + + + + + + + + + + + +
5+,+ B # 6 + + + + + + + + + + + + + +
5 7 + + + + + + + + + + + + + + + + + + + +
6 7=
91
90
9,
9,
95
O094A 6! /$ 04<%A9& J A$/AD
) & ' . # + '#
(
'#! 0 ) + ' '#! ( ( ' * ( Q 1R !
( + B
+ '#! < 3!6!2
@ + ? 7 + '#!
4 + '# ' ( 1! 1+ 6!3 H
> (a) 1+ + '# 33 # > + ) ? # + ) ? # + - ?! D 1+ 2 ( Q 1R + ( Q R `)( !
J + (b) -! . QR # + # ' )
Q R + (d) 1 (c)
# P # + # ! (c) (d) 2 1+ 3!;
H - + '#!
< + +!
) * 5 + '# ( : + - ) + '# # ) + !
7;
O094A 6! /$ 04<%A9& J A$/AD
4
4
3
3
3
3
3
3
5
4
5
4
3
3
3
3
4
(b)
(a)
5
4
3
3
4
3
3
4
4
4
3
3
(c)
(d)
6!3 T !" # ! $ % " '
( - ! 4 ( 1 + '# A n (n + 1)e 1! ∆ A∆ +
A + +! : ∆ A∆ Q 1R : 1+ 6!3! : : +!
D : + ' n # Q# R Q# 1R!
=8
O094A 6! /$ 04<%A9& J A$/AD
'
,
! )+ 0 *
: +! )+ # : # !
T # * : +! /
1+ 6!3 # + ! D ! ( !
T #, + # - + S
# + !
T # )
QR + Q R! A + ∆ ( # !
A 1 )+ #, - + '# 1 !
] + # # S
+
2 n! D '# >
'# n pk # k S 3 k n p (n−2) (p3 , . . . , pn )!
( ) 0 +
9 # p ) + '# n 7 + '# B * p
1+ 6! ) K3; ! 2;?L!
6! T (# 4 p = (7, 12, 3, 0, 0)
=3
O094A 6! /$ 04<%A9& J A$/AD
'#
% 2 & &! 3
5 8 !
D +V + '# ? ! ] - @ ! D 3!6!2 - ]! - 6 p > @ ; 8 3 I @ = 8 I 7 @ 2 8 I ] 38 8 @ 8!
1+ 6!2 6 + '# ( !
I
II
III
IV
6!2 T 5 $ 6 < 6 - + '# * ) B ( : +
6 1+ 6!6 6!7! D 6 + '# Q R
1+ 6!2!
? + @ - ) - > # ( + @ # + @ 2 #
+ - 1+! 6!6! ) 98 =
O094A 6! /$ 04<%A9& J A$/AD
Symétriques, hexagones bornés :
b
a
c
Symétriques, faces hexagonales découpées :
d
g
e
f
Chiraux
6
i
j
h
6!6 T 01 7 8 p = (6, 9, 0, 1) ) 4 7
#
-! / * 38 32 ) B 7
) - 2 ( + ! ( 3 2 ( # @ ! ( + -!
+ - H )
- ! # + = # + @ # + ! 0 + > + a b
98 =2
O094A 6! /$ 04<%A9& J A$/AD
1+! 6!?! a 3 + ? + b 6 + ! 3= ( # [email protected] !
+ - 7 + @ + 2 + ! /
S - 2
+ 1+ 6!2!
0 32 ( 2 + # # ! 0 -
( 1!
A 1 + QR # + @ # + * @
+ 2 + ! C + (( -
# 1+ Q+ R # + ! -!
98 A1 + - ] * ) ]! ]! 1+ 6!7 ( ! 38 + @ ( + # + ! D - 2 > + 2 + 2 + @
+ 2 + !
98 1
. 4 $ D 1 @ + 3!6!2 #, >
'#
! !
! - 3
38
32
- 3
3=
[email protected]
- 3
32
@
- ]
3
6
6
62
7;
6!3 T ( 6 =6
O094A 6! /$ 04<%A9& J A$/AD
2 pentagones bornés :
b
a
1 pentagone borné :
c
f
e
d
g
i
h
k
j
m
l
n
0 pentagone borné :
o
6!?
#
T
p
q
09 7 88 p
=?
r
= (6, 8, 2, 0)
O094A 6! /$ 04<%A9& J A$/AD
2 pentagones bornés
5
5
5
5
5
5
b
c
a
5
5
5
5
d
e
1 pentagone borné
5
5
5
f
g
5
h
5
5
i
j
k
0 pentagone borné
l
m
[email protected]
#
T
0 7 888 p
[email protected]
= (7, 6, 3, 0)
O094A 6! /$ 04<%A9& J A$/AD
a
b
6!7 T , 7 8: p = (10, 0, 6, 0) #
#
=7
O094A 6! /$ 04<%A9& J A$/AD
==
)
/ ( + )
+ B , 1+ Q R!
0 ) µ λ
1 ( + + +! D ) + ' 4+ + ( + !
0 1 1 + + ) + ( B !
=;
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
*
*
*
#
0
"
"
'+0+0 ? + + + + + + + + + + + + + + + + + + + + + + + + + + C0
'+0+, - . + + + + + + + + + + + + + + + + + + + + + + + + + + + C,
/ 0
µ
'+,+0 (% + + + + + + + + + + + + + + + +
'+,+, . µ + + + + + + + +
& 3 +
&0 λ
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
C
C
C
C'
"%
!!
'++0 (% + + + + + + + + + + + + + + + + + + + + + + + + + + C9
'++, - λ + + + + + + + + + + + + + + + + + + + + + + + + + C9
'++ = λ + + + + + + 011
*
**
2
*-
- . + + + + + + + + + + + + + + + + + 011
- . + + + + + + + + + + + + + + + + + + 010
'+'+0
'+'+,
'+'+
'+'+5
3
0 1
8 + + + + + + + + +
( * - # $ + + +
+ + + +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
;8
+
+
+
+
!
010
01,
01
015
!*
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
+
! *
J + ! + * ( + '# ( ! D # > !
$ + A(D) Q R + ( U ! ( + * # ) ) + 1+ ?!3!
3
4
4
# * H # 2
3
2
1
1
(a)
(b)
?!3 T ! " . 1 + > 1 + # 1 ( ! 5 * 1
) Q R! D 1 ) + ( #
+ (!
4 / ( , ) ( (O, i, j)! D 1 ( >
) ( Di + ) (ai , bi ) ai x + bi y + 1 = 0 ) (θi , di )
N θi ∈ [0, π[ + ( : (Ox) di ;3
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
+ + cos(θi ) = ε −bi
a2i
+
b2i
,
>
1
di = ε 2
,
ai + b2i
ai
sin(θi ) = ε 2
,
ai + b2i
ε = sgn(ai )!
/ ( Di >
cos θi
x
− sin θi
+t
= di
cos θi
sin θi
y
Ni
Vi
# P Vi Ni Di −−→
' Pi + Di : OPi = di Ni ! 4 Pij Di Dj !
Di
Ni
θi
di
Pi
Vi
?! T $ Di ai < 0, bi > 0, di < 0
/ D + ) ( : ' B + !!2 > 0 = θ1 < θ2 < · · · < θn < π N a1 = 0! + + +!
D Di # (a, b) ∈ R2 (θ, d) ∈ [0, π[×R! ) (a, b) * 1 (θ, d) 1 + + !
*,
1 1 + 1 ) µ + + λ + +
;
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
+ !
+
+ *
) * µ
( ) ) + 1 !
( %) θn+1 = π
1 ) µ ∈ [0, 1]
µ=
!
(θi+1 − θi )
(θi+1 − θi )
+ µ 1+! ?!2 # + * 2
+ > 0, πn , 2 πn , . . . (n − 1) πn ! + > n + !
µ = 0 +1 ) + +
µ ( 8 Q R ) ! µ + + Q R!
4
4
3
2
3
2
1
1
?!2 T ;# . µ 5 5 !,
µ ! ! 5 . 4
A 3;[email protected] ! 4+ ' # ( ) K2L ]+ K6 ! 63L! ' *
;2
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
#, >
. 0
$ (
. ' ' + µ = 1 + !
O 3;[email protected] ' # K6L!
A 1+ ?!6 + @ # '!
( K6 ! 6L + ( - + !
( ) D 1 $
# ' 4+ !
+
8 . J5K ) 0C96 : J6K # $
L $ # $ , + 8 0CC0 / J0K # $ 6 % '+5
a) '+'+
(a)
(b)
?!6 T (# ? : J5K ) 6 % '+5 a) !*" ! " %
'+' M + D1 $ D6 α1 < · · · < α6 +
;6
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
- β1 = −1, β2 = 0, β3 = 1, β5 = 9, β6 = 10+ ? β4 H ]1, 9[ + A # β4 = 32 +
/ P Q (1, 10)+ R (r, 0) S = D3 ∩ D5 )
9r+81
( 9r+9
8 ,
8 )+ ( % (QR) )
10
8
β(QR) = 1−r
< β1 = −1 M r > 11+ (M (P S) ) β(P S) = 1 + r+1
> 53 +
β4 > β(P S) > 53 +
5
4
6
3
S
Q
2
R
P
1
?!? T # /
: ' ; A µ B ' >
. n 0 3
[0, π[ ! 0, , , . . .
(n−1)π
n
π 2π
n n
' B # + 1+!
?!6 b ( ! *( 1 ' µ = 1 +!
) - % '+6+ ? π/6 +
? 7 ) D1 , D2 , D3 0, π/3, 2π/3
(ABC) A = D1 ∩ D3 B = D3 ∩ D5
C = D5 ∩ D1 7 G+
? D2, D4 , D6 α, α + π/3, α + 2π/3 α ∈]0, π/3[ (A B C )
A = D2 ∩ D4 B = D4 ∩ D6 C = D6 ∩ D2 + = P2 , Q2, R2 ;?
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
D2 D1, D3 , D5 P4, Q4 , R4 D4 D3 , D5 , D1 % P6, Q6 , R6 D6 D5, D1 , D3 +
D4
D3
D5
P4
D6
B
Q4
R6
B’
D2
G
h
R2
C’
A’
Q2
α
P2
d
D1
C
A
R4
Q6
P6
[email protected] T 3 0
? (AB C ) G 7 , . )
α d = P2 A = P4B = P6C h G $ [A C ]+ D1 , D3 , D5 %# D2 , D4 , D6 α d+
+ D d P2 $ A+ 8
(A B C ) (ABC) S G α ρ(α, d) # α d+
A d %# P2 %# 7 α ) D2 (α) A G+ D 3
7 D2 G $ % '+4 (a) ) A C D2 + = ) D2 D4 , D6 ) h +
;@
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
D% )
∂h
<0
d α h )
∂α
∂h
<0
α d h )
∂d
8 # α d 1 P2 A (AG) π/6+
= % α < π/6 # π/6+
D4
D4
D3
D5
D3
D5
P4
P4
D6
B
B
D2
Q4
D6
R6
R2
A’
C’
B’
D2
G
G’
h’
Q2
α
R2
C’
A’
B’
P2
G
D1
C
Q2
P2
α
C
A
A
R4
D1
Q6
P6
P6
(a)
(b)
?!7 T 3 ,
/ (AB C ) $ G
G h G $ (A B C )+ -
5 ) α d2 = P2 A, d4 = P4B, d6 = P6C +
? dm = min(d2 , d4 , d6 ) dM = max(d2 , d4 , d6 )+ ? % hm (α, d2 , d4 , d6 ) + hM (α, d2 , d4 , d6 )) G Tm + TM G . (α, dm ) +
α, dM + 7 )
hM (α, d2 , d4 , d6 ) h (α, d2 , d4 , d6 ) hm (α, d2 , d4 , d6 )
D > D +
# ( )
+ # ' 4+ µ = 1!
$
;7
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
+
#
%* λ
( ) D ) µ ( 8 + ! + > µ = 1
+ ( 1+ ?!3 b
N Q+ R # ! 0 # # + 1 ) +
+ + !
( ) 9 ' [0, 1] 1 + * !
1 ?!3!3 ) λ ∈
+ µ ) λ Q R +
+ ( +
+ * + +1 # !
> λ = 1
* E n = 3
+ + + ! 0 n 4 ' λ < 1!
D λ n = 4, 5 ( @!
#
*!
λ
.
* +! * Di ½
' S - 1+
Dj Dk i
i
!
?!= D αjk + ljk
1 Dj
Pjk
αjk
i
D
Pij
D
i
k
?!= T % i, j, k ½
;=
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
D
γ = i, j, k & 1=0
)
i
ljk
=
|ai bj − aj bi + aj bk − ak bj + ak bi − ai bk |
|ai bk − ak bi | |ai bj − aj bi |
γ
: aγ x + bγ y +
a2i + b2i
) 8 # G )
1
Pij =
ai bj − aj bi
bi − bj
aj − ai
Pik
1
=
ai bk − ak bi
bi − bk
ak − ai


bi − bj
bi − bk
 ai bk − ak bi − ai bj − aj bi 


−−−−→

Pij Pik = 


 ak − ai
aj − ai 
−
ai bk − ak bi ai bj − aj bi
−−−−→
Pij Pik
(aj bi − ai bj ) + (ak bj − aj bk ) + (ai bk − ak bi ) −bi
=
(ai bk − ak bi )(ai bj − aj bi )
ai
(aj bi − ai bj ) + (ak bj − aj bk ) + (ai bk − ak bi ) a2 + b2
= i
i
(ai bk − ak bi )(ai bj − aj bi )
+ # # # E
. + # ) Dj (aj , bj ) - Dk >
a (b − bi ) + bj (ai − ak ) + (ak bi − ai bk ) i
2
2 j k
ljk (aj , bj ) = ai + bi (−aj bi + ai bj )(ai bk − ak bi )
i
+ * ljk
# ( + ( (aj , bj )!
)
Di (ai , bi ) >
a (b − bk ) + bi (ak − aj ) + (aj bk − ak bj ) i
2
2 i j
ljk (ai , bi ) = ai + bi a2i bj bk + b2i aj ak − ai bi (aj bk + ak bj ) . + # # !
+ λ + P
* H B - λ *
! ( )!
;;
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
##
λ ! ) λ 1 >
( ) 0 +
!
< *
+ * !
> * λ 1 > ) λ (+! ( ) !
λ # + # + # - + ) Y !
A B λ )
+ * * +
# > * * # ) Df Q R! Df
1 + λopt !
/ N + ) 1 * ( 6 ? !
+
* ,
/ ) + + λ + µ + ! * ) * ( ( + + + # # +!
0 ) ( + ! D ) σ # + λ Q R Q+R # + ) + ! ) H ( + > H κ #
( # κ (+ σ ! Q R + σ 388
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
)!
* A 1 λ P ) ) # I + ( ) # !
" A ) λ µ #, !
A +
+ ! µ = 1 : * ! < µ = 1 + @!3!3 !
+
n )
+ λ ! ] / λ µ ) [0, 1]! < ) ν >
ν(A) = α µ(A) + β λ(A)
++
α + β = 1, α > 0, β > 0
- + ( + + ) ( ! ) λ ( ! D # ( + (!
&
# + #! 32 ! 6! + ( - + λ ( ! ) > ( + B# 1 # !
383
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
( - D ! 4 +! ) * : D H ' 1 X 1+ ?!; ?!38!
4
5
3
4
5
3
F
G
F
O
D
3
6
6
6
4
5
G
G
2
2
2
D
D
C
E
B
1
A
B
E
B
1
A
E
(b)
(a)
1
A
(c)
?!; T ( * < D : ) * D 2 1+! ?!;! . *
AE, EB, BF, CG, DG ?!; a! / + n − 1 * !
/ * * # ( ( -
+ ! ?!; b (E, F, G) (A, B, C, D) # (A, B, D) C ∈ [BD] !
A1 1 # ( D ! . ?!; c (E, F, G) (E, G) # (A, B, D) *!
38
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
6’
B’
A’
E’
5’
4’
3’
2’
1’
F’
G’
D’
?!38 T ( * < ) / #, 1+ ?!; 1 6 : A G ! + + B , E G > 3 A G !
& -+ 2 = (BD)
G ∩ E = (GE) A ∩ G = (AG)
2 [1, 2 : 5, 6]
[2, 4 : 5, 6] >
((
6 ) 0 D1 , D2 , D3 , D4 [D1 , D2 : D3 , D4 ] D1 ∩ D2 ) D3 ∩ D 4 !
B ' + + ( + !
#
*
2
. $ 0 + n - k λ 382
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
>
T *
T T *
T . @ * +
* +
2 + λ!
0 ( + ( ( + ( k !
'
D # + (+
! + ( λ B # ( *! ] + ( # >
# 0 , ! ) 9 :
& $% ) ,
#4 ) ! * ; ) ! ! * ; ) ) < =
< * &
>&&&=&? $ 4 1 # 4 2 ) &
: < &
) 9 @ 386
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
A $ [email protected]
# & & $ &
# & & & & 2 ,
&
+ :
2
: A @ 1 A
1 @
& &
& A @ +
: :' B : C :' D 2 ! 45
' + ( λ + ( + + ) ' + # - λ λprec #
1.01 ' * +!
$ + ( ( Q R !
+.
/ 1+ + ( ! + H # P # Q + R !
A )+ + Rconv = 1, 01 * ) :
* ! + 1 Rconv = 1, 001 1, 0001!!! ) 1 ! + ' C ) !
38?
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
?!33 T = 4 ) % λ = 0, 0031 λ = 0, 0603 9 ×20
[email protected]
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
?!3 T = 0, ) % λ = 0, 0023 λ = 0, 0141 ' ×6
387
O094A ?! <09.9<D /A 4A045.AD99<D A$/ADDA
?!32 T = ' ! " ) % λ = 0, 0389 λ = 0, 6181 6 ×16
38=
*
/ ( + ) + λ ( !
/ 1+ 6 ? ! - λ
S ' + # λopt = ϕ−1 6 ? !
/ ) ) + + 1 ' 4+ ! ( ) ! D 1 ( )
# + ( B + + + ) µ!
38;
O094A @! . 049$A4.
-
-
2
6+0+0 -
6+0+, -
) + + + + + + + + + + + + + + + + + + + + + + 000
n = 5 + + + + + + + + + + + + + + + + + + + + + + 00'
n=4
4 6+,+0 > + + + + + + + + + + + + + + + + + + +
6+,+, 2. + + + + + + + + + +
- + + + + + + + + + + + + + + + + + +
6+,+ 8 + + + + + + + + +
+ + + + + + + + + + + + + + + + +
7 + + + + + + + + + + + + + + + + + + + + +
338
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
.
004
00C
00C
0,1
0,0
0,0
0,0
O094A @! . 049$A4.
.
- $ / + + !
-!
3
*
n = 4 ( 3!6
6 + 1 )!
A ) 6 = ) - !
) n = 4 $ π/4 µ = µ = 1 1 √
4 µ = 15 λ = 2 − 1 ≈ 0, 414(
≈ 0, 618 . λ ! λ = ϕ =
0, , , 1 µ = 1/2(
& )
opt
max
2π
5
D3
3π
5
D
opt
4π
5
√
−1
5−1
2
2
D3
∆
D2
D4
D4
∆
a
b
O
D1
1
A
b
a
b
O
1
D1
b
@!3 T n = 4 ) $ λopt = ϕ−1 µ = 1 : λmax =
) √
2−1
% 6+0 $ . λ $ 5 + 8 λ µ = 1+
D1 , D2 , D3 , D4 %# $ . O = D1 ∩ D2 D3 x = 1+ A 7 C = D3 ∩ D4 ∆ D1 , D2 π/8
333
O094A @! . 049$A4.
# . + D 3 . C
D4 # . λ+
2 7 9 b
0 a b + , , √5 # + %+ = λ = Max(1,a)
= Min(b, b/a)+
- b/a = 1/√ 2 ≈ 0, 707+ ( C √= D3 ∩ D4 = D3 ∩ ∆ (1, b)
M b = tan(π/8) = 2 − 1 ≈ 0, 414+ ( λ = 2 − 1+
A $ λ + = D1
* θ2, θ3, θ4 D2 , D3 , D4 %# +
2 7 C ∈ ∆ % 6+, (ACE) (BCD) . C + ? δ = θ2/2 ∆+
D3
D2
D4
D
∆
E
H
C
a
b
O
A
c
D1
B
@! T 7 $ n = 4
= D1 D2 O(0, 0) $ 3 D1 D3 A(1, 0)+ = 7 . 7 θ2 θ3 G $ θ4 # )
= Ê = CEH
+
( (ACE) ) Â = CAH
= π/2 − δ CAH
= Â = π − OAH
− θ3 = δ − θ3 + π/2+
( OAH
(M Â = θ2/2 − θ3 + π/2+
= π/2 − δ CEH
= Ê = π − OEH
− CED
= π − (π/2 −
/7 OEH
δ) − (π + θ2 − θ4 )+ (M Ê = θ4 − θ2 /2 − π/2+
D Â = Ê θ4 = π − θ3 + θ2
6+0
? # a = BC = CD b = AC = CE c = AB = DE +
- b = AC +
33
(ABC) (CDE) O094A @! . 049$A4.
∆ y = x tan δ D3 A(1, 0) y = (x − 1) tan θ3+
tan θ3
tan δ tan θ3
= ) C = tan θ − tan δ , tan θ − tan δ + (M
C
3
b2 = (xc − 1)2 + yc2 =
tan2 δ(1 + tan2 θ3 )
(tan θ3 − tan δ)2
3
tan δ
b=
(tan θ3 − tan δ) (cosθ3 ) λ # (ABC) (CDE) . # θ2 + - (ABC) $ +
) (ABC) . A AC = b = c = AB
$ µ = 1 % = π − BAC = π − θ3 + = ABC
= π − θ4 + (M
ACB = ABC
2
2
2θ4 − θ3 = π
6+,
( 6+0 6+, )
θ3 =
π + 2θ2
3
θ4 =
2π + θ2
3
θ2 < π;
π
< θ3 < π;
3
2π
< θ4 < π
3
D H # b θ3 δ θ2 . % )
b = 2 sin
θ2 π
+
3
6
−1
6+
( (ACB) # A θ2 π
θ3
= 2 b sin
+
= b (1 + b)
a = 2 b sin
6+5
2
3
6
8 θ3 > π/3 2 sin(θ3 /2) > 1 a > b+ = b
b(θ2 )
= min b,
(θ2 )
λ(θ2 ) =
max(1, a(θ2 ))
a
8 $ b(θ2 ) ab (θ2) [0, π]+
8 b(0) = 0 b(π) = 1 b [0, 1]+
1
( ab (θ2) = 1+b
(θ2 ) 1 0 1/2 π N # %+ 6+ +
8 # [0, π] # λ+ = % θ2 = 2π/5 √
λopt = λ(2π/5) =
1
5−1
= =ϕ−1
2
ϕ
332
O094A @! . 049$A4.
3π
4π
, θ3 =
, θ4 =
D . # ) θ2 = 2π
5
5
5
$ 7 . $ % 6+0 +
Cas 1 : (ABC) isocele en A
Cas 2 : (ABC) isocele en B
2
2
b
b/a
b
b/a
a
1.5
1.5
1
1
0.5
0.5
0
0
pi/6
pi/4
pi/3
2pi/5
pi/2
4pi/6
5pi/6
pi
pi/6
pi/5
pi/4
pi/3
2pi/5
pi/2
@!2 T > θ2
. B AB = c = a = BC
θ4
π − ABC
=
= θ3 M
= + = BAC
BAC
ACB =
2
2
)
(ABC)
6+'
θ4 = 2 θ3
( 6+0 6+' )
θ3 =
π + θ2
3
θ4 = 2
π + θ2
3
θ2 <
π
;
2
π
π
< θ3 < ;
3
2
2π
< θ4 < π
3
8 H # b θ3 δ . % )
θ2 π
−
+1
b = 2 sin
6+6
3
6
( (ACB) # B b = 2a sin((π − θ4)/2) b
= 2 sin
a
π − θ4
2
= 2 sin
π θ2
−
6
3
=1−b
6+4
B b(θ2) ab (θ2) [0, π/2]+ = % %+ 6+ b(0) = 0 b(π/2) = 1 b #+ ( . 6+4 b/a = 1 − b ab (0) = 1 ab (π/2) = 0 ab #+ D b < a [0, π/2]+
λ min b, ab # b = ab = 1 − b M b = 1/2 λmax = 1/2+ θ2 = π/2 − 3 arcsin(1/4) % % 6+5+ % (ABC) . B λopt +
336
O094A @! . 049$A4.
D3
D2
D4
∆
1
b
O
1
1
A
B
D1
@!6 T (ABC) . B ) λoptB = 0.5
) (ABC) . C
- D1 D2 . +
D % A λ +
3
*
n = 5 3!6
? @ + - ) 1+ @!?! +
# + ( ( ! 0 ( λ
+ + + 1+!
/ #, : + ) λ + + + ! λopt *
6 > λopt = ϕ − 1! + -+ ! 1+ @[email protected]!
+ * b = AC
b
? a = AB 38 λ = !
a BD
BD
< + ( ( (OBD) (OB D ) N
=
OB
OB
b+a
b
!
=
a
b + 2a
A B + < b2 + ab − a2 = 0
>
a2 λ2 + λ − 1 = 0
33?
O094A @! . 049$A4.
b
b
d
d
a a
e
e
a
a
b
d
c
a
c
a
b
b
b
a
b
d
a
c
a
c
c c
λ = 0.55
a
b
λ = 0.35
c
c
c
c
b
b
d
b
d
a
e
e
c
a
a
b
b
a
b
b a
d
a
b
a
b
c
d
c
λ = 0.31
θ = (0, 2π/9, π/3, 2π/3, 7π/9)
c
λ = 0.17
θ = (0, π/5, 2π/5, 3π/5, 4π/5)
c
b
b
a
e
a
d
b
f
h
b
e
b
a
b
g
b
a
a
a
a
b
g
c
b
b
b
b
λ = 0.618
θ = (0, π/5, 2π/5, 3π/5, 4π/5)
λ = 0.31
@!? T 6 ' [email protected]
O094A @! . 049$A4.
D
E
D’
Ω
C
a
b
A
B’
a
O
B
@[email protected] T √
A λ < 1 1 λ = ϕ − 1 = ϕ−1 =
.
5−1
!
2
0 / + ( ) +
1 !
3
6 D , + D = {D1 , . . . , Dn } n θi ∈ [0, π[ + Di ( : + #, 0 θ1 < · · · < θn < π ! + + ) !
D θ # ( + 1 >
θ(Di ) = θi !
( ) $ + D = {D1 , . . . , Dn } n 3 >
T Di A(D \ Di ) * S Di ! Di > 1 = $
337
O094A @! . 049$A4.
+ Q R 1 ) *!
T + (n − 1) D \ Di * !
< + D n (Dσ(1) , . . . , Dσ(n) ) N σ ∈ Sn
D \ {Dσ(1) , . . . , Dσ(k) } 0 k n − 1!
>
σ ∈ Sn 1 #, + D !
1 ) + # ! / N 1 + + >
Di ri +
Di n # + D !
D Rd(D) = (r1 , . . . , rn )
< n + + Di,1in !
( $) < $ +
D4
D3
D4
D3
D4
D3
D2
D2
D5
D2
D1
D5
D1
D1
(a)
(b)
@!7 T (c)
(a, c)
(b)
- $ 5 (a) ) # !# " 0 D1 D2 % 6+4 # ! "
, D3 D4 +
A 6 $ ' ) (b)+ A # (c) ,5 $ (D3 , D2 , [D1 , D4 , D5 ]) (D3 , D4 , [D1 , D2 , D5 ]) (D4 , D3 , [D1 , D2 , D5 ])
(D4 , D5 , [D1 , D2 , D3 ]) M [ ] + 8 ) Rd = (r1 , r2 , r3 , r4 , r5 ) = (3, 2, 1, 1, 2)+
A 5 $ 6 5 ,4 + 8 )
33=
O094A @! . 049$A4.
O
O
O
O
' 7 8 ) 8+ < 8+ $ 8+
0 7 88 ) 88+ 88+ < 88+ $ 88+ < 88+ $ 88+
C 7 888 ) 888+ $ 888+ < 888+ $ 888+P < 888+
7 8:
D # n = 5 n # 7 $ n I + - # ) n = 7 # % 5+, $ +90 I +
A # n 7 +
> 1 D n 3 (
) 5
)
8 G +
- % I Di Di Di I Di +
A Di +
- D+
+ + + ) + ) !
3
$
90 ? $ D n 3 $ $ 0 0 θ < · · · < θ < π(
) 90
$)
1
n
? D +
33;
O094A @! . 049$A4.
A D σ1 , . . . , σn θ1 < · · · < θn +
? 7 . m Q m ) Dm m I Dm Dm $ +
7 . . I +
A m = 3 $
+ 8 +
m+1
/ Q m Dm+1 = (D1m+1 , . . . , Dmm+1 , Dm+1
)
m+1
m + 1 I Dm+1
+
A Q (D1m+1 , . . . , Dmm+1 ) $ I + I R −→ R2m A(D1m+1 , . . . , Dmm+1 ) B(O, r)+
m+1
= $ I $ Dm+1
T
$ R > r . $ + m+1
Dm+1
I +
m+1
; Dm+1
R(O, θ) H $
$ +
m+1
Dm+1
A(D1m+1, . . . , Dmm+1 )+ m+1
m+1
Dm+1
) θ(Dmm+1) < θ(Dm+1
) <
m+1
θ(D1 )+
T I R(O, θ) Dm+1 $ . +
7 . $ 7 . . $ + *
+ 1 ' 4+ ( ?!!! A * + µ = 1! + ) + λ * ) !
> ( ) H + 1 ' 4+ ! # > + + + 4( 38
O094A @! . 049$A4.
.# K23L '
4+
) @ ! + # !
3#
. 0 + + !
+ ( I > + Q R + #, ' +!
0 + D = {D1 , . . . , Dn } + 0 θ1 < · · · < θn < π + D = {D1 , . . . , Dn } D ∀ i, θ(Di ) = θi ! 0 Q R D B *
D !
. (Dσ(1) , . . . , Dσ(n) ) + D + B
> u1 = σ(n), u2 = σ(n − 1), . . . , ui =
σ(n − i + 1), . . . , un = σ(1) + ( ) ( !
T 0 i = 1, 2
T Dui + θui O !
T 0 i = 3 > Du3 + θu3 3 O
T 0 i = 4 n
T B(O, r) A(Du1 , . . . , Dui−1 )
T Dui + θui 2r O
T & i
3 8
+ ( ( ) !
+ ( n ! ( i C ' ! 0 # i − 1 ' !
33
O094A @! . 049$A4.
A 1 + ( B O(n2 ) + (!
* 0 + + ( B
) µ + 1 π/n!
3
+
' () - # (( #
# +1 # ( # !
) 1 ( 1 + (+ ) ! 0 # ` ( + 1 (
(+ !
/ + B
+ ( + ) # # + +1#! + + ( 1 * # + ( ! * * + !
) ) ! λ * ) +! ) λ (+ # + ( * * !
( *
! A + ( λ 32
1 + + ) * + + - # Q R
* ! . H + # + > - * + ) !
A ) + + - P Q # R + > + Q R ( (
? # ' 4+ ! + ! QR + ( Q R! ) ( + + ( C * (
+ + !
A1 + +
+
+ + 1 ( @! /
+ - + 1 Q #R (! / + Q +R + + ! A1 + +
' 4+ ! # + +
#, + !
/ + ( # ' * ' ( !
36
, @ % ) K3L 0! Z! +a !
! + $ - 0
3;;3!
KL <! (( : &! ( O! Z ! A+ - # a( ! + 33T3=! 0 883!
) ( 2: % / A /
K2L <! (( : O! Z ! 9(
# ! - > ) ( 2B % A A A / AAA #CC2 + 37T8 883!
K6L ! "'b ! ]+ "! .# D! c( ! d+ ! , [email protected] # / % ! + $ 0
3;;2!
% ! A 3;;?!
! d ,$+ ! 0(/ ( K?L %!/! " ! e!
[email protected] A! "
$ - # c (+ . 3;;8!
K7L Z! ! X O! A ! %! ! .( A! c : !
- # + # # !
9( / # . $ - # $
( + D 3;==!
K=L ! O! A .! ( .! c (! + X ( X
X !8! 9( 4 94.83;= $ - # (+
3;;=!
K;L ! "+ 0! " <! ( + 0! ! < #-+ !
88!
3= A c X (
- 88!
A / 6% / ) $! 0(/ ( K38L &!4! /+ !
% ( & 3;;3!
$
K33L /! 0! / X ! %! : ! 0 # ( # (
! 3;=7!
) ( B A */ ( A ( /
3?
""<40OA
K3L /! 0! / X ! 9 ! AH # +
a( ! + ;2T283! 0 883!
) ( 2: % / A /
K32L O! A !
3;=7!
% A $ /!
. +] +
K36L O! A ! %! 0( 4! 0 X 4! . ! .(!
+ # ( +- + ( !
+ 23;[email protected] 3;;!
6% A * K3?L /! A A! ! 9! 9 ! < # !
33 >333T36= % 3;;@!
D( % # +
[email protected] %! A! ! 0 # # ' # +W 32 >7T2? 3;=8!
K37L %! A! %! <4 X!
! 4 0 3;;7!
% /
K3=L %! A! 4! 0
32 >6=6T?87 3;=2!
K3;L "! W!
3;@7!
< $; A X! A )/ !
+!
*@ D( A (
( 3=! % ( c - f . ) ( # . A ( K8L "! W! + # (- ! + [email protected] 3;73!
A $ (
% 6% / A (
A ( * ( %(
K3L "! W! + ! + [email protected]! ! (! . ! 0 3;7!
KL ! %! . 1! 0 # ( # +
( # M + !
6 >76T32 3;=?!
A 6 ( %
K2L %! O # 4! 9'! AH
36 >?6;[email protected]= 3;76!
- +!
D A
? $ ! 0(/ ( $ 0 . +
K6L ]! +!
3;;?!
K?L 0! (! . : !
# +
3;=;!
A CEF:F2B2EBGEFGCCC9GC##E
[email protected] 0! (! 9
+ # - > a( + : !
23 %&
3;;3!
A K7L 0! (! + : # !
26 3;;6!
62 >7?T
@ ( D( A ( / H [email protected]
""<40OA
K=L O! A 0! " .!Z! c (! 0
E
# + + ( !
A $ ! $ $ ! 0(/ ( $ % ( & K;L Z! ] 0(!
3;;6!
K28L &! 0! 0 ! ! .( !
. +] + 3;=?!
A / @ !
K23L %! 4( "! .# ! < ( +- + # - !
2? >2=;T63 3;;3!
6 ( %( *(
K2L ! 4+ ! 9 + A ( 9
[email protected] >7;T38 3;[email protected]!
%( I(
+ ( !
* J K / k ! 0(/ ( $ O 3;;?!
K26L D! . ! </ A J- ! 0(/ ( .a & # 9( +- dW( 888!
K22L /! .(!
K2?L D! . ! & ! O- '! <C!
[email protected] ! ]+ ! < + !
D( A $ ( 6% / * ( L
K27L .! c (! + X! CC""" ; *;
,;C
# ( ' # +!
63 >[email protected]; 3;[email protected]!
CC""";;
37
;CE" C=
C!
""<40OA
3=
.<=:><
+ + + ( + +
( +! D (( + ( H # +
# 1 !
+ + 1 + ' 1 ( + (
+ ! + ( ) Q R + ' 1 ! D + - ) !
37=9.39
+ ( a - + - # ( + - + -! < - ( ( # + ( H ( # + # ( # (:+ ( + ! O a ( - # ( + # + - (
1 # + a a # (
! 9( ( ( ' 1 # ( + : + ( a ! 9( + (
#- ( + Q R # + ( a ! c + -
: # + a( - #a !
/
1/--страниц
Пожаловаться на содержимое документа