Eps1 1
Eps2 1
Figura 3.1: Exemplo da interface gr´afica interativa. +
3.2
Caracteriza¸c˜ao da fun¸c˜ao Eps
Come¸camos por fixar algumas nota¸c˜oes e referir algumas liberdades de nota¸c˜ao a que nos permitimos.
Nesta sec¸c˜ao, os conjuntos considerados s˜ao subconjuntos compactos de R2. Usaremos letras mai´usculas para representar pontos e conjuntos de pontos.
Iremos representar da mesma forma, por uma letra mai´uscula, um ponto e o conjunto singular formado por esse ponto.
Um segmento de reta ser´a identificado pelas suas extremidades; o segmento de reta definido pelos pontosA e B ser´a denotado por [AB].
Dada um sequˆencia de n pontos A1, . . . , An, n > 1, a linha poligonal definida por
essa sequˆencia de pontos, correspondente `a uni˜ao dos segmentos de reta [AiAi+1], i =
1, . . . , n − 1, ser´a denotada por [A1. . . An]. Observe-se que, nesta defini¸c˜ao, uma linha
poligonal poder´a corresponder a um segmento de reta.
Representaremos por Funcao a implementa¸c˜ao da fun¸c˜ao “Funcao” no sistema Mathe- matica.
Dados dois conjuntos X e Y , o menor valor de ε ≥ 0 cuja vizinhan¸ca-ε de X cont´em Y ser´a denotado por εX,Y, i.e., εX,Y = minε ∈ R+0 : X(ε) ⊇ Y .
O objetivo ´e construir2 uma fun¸c˜ao Eps tal que, dados conjuntosX e Y de determinada
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 30
forma, Eps[X, Y ] = εX,Y. Ambicion´avamos que qualquer um dos argumentos da fun¸c˜ao
Eps pudesse ser um ponto ou uma linha poligonal no plano, mas fic´amos aqu´em desse objetivo.
Os argumentos da fun¸c˜ao Eps s˜ao muitas vezes referidos como objetos.
Nesta sec¸c˜ao s˜ao apresentados alguns resultados que permitem definir e justificar o algoritmo desenhado para a fun¸c˜ao Eps. O primeiro desses resultados ´e um lema gen´erico, uma vez que invoca um conjunto que n˜ao ´e necessariamente um ponto ou uma linha poligonal. Este lema ser´a usado na demonstra¸c˜ao de alguns dos lemas subsequentes. Lema 3.1 SejaX um conjunto compacto3 n˜ao vazio eP um ponto. Ent˜ao,
εX,P = d(P, X).
Demonstra¸c˜ao: Como P ∈ X(εX,P), existe um ponto A ∈ X tal que P ∈ D(A, εX,P).
Conclui-se ent˜ao que d(P, X) ≤ εX,P.
Por outro lado, qualquer que seja B ∈ X, d(B, P ) ≥ εX,P logo d(P, X) ≥ εX,P.
Conclui-se assim qued(P, X) = εX,P.
A situa¸c˜ao mais elementar ´e aquela em que cada um dos argumentos ´e um ponto. Lema 3.2 SejamA e B dois pontos. Ent˜ao
εA,B = εB,A = d(A, B).
Demonstra¸c˜ao: Este resultado decorre do Lema 3.1 considerando P = A e X = B ou
P = B e X = A.
A fun¸c˜ao Eps, no caso em que os argumentos s˜ao dois pontos, limita-se a calcular a norma do vetor definido por esses pontos.
A Figura 3.2 apresenta um exemplo de aplica¸c˜ao da fun¸c˜ao Eps quando cada um dos argumentos ´e um ponto.
O pr´oximo lema permite-nos definir a fun¸c˜ao Eps quando o primeiro argumento ´e um ponto mas o segundo ´e uma linha poligonal.
3O resultado ainda ´e v´alido se substituirmos compacto por fechado. No entanto, nesta sec¸c˜ao estamos
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 31
A =H0, 0L
B =H1, 1L
¶A, B= ¶B, A= 2
Figura 3.2: SendoA e B pontos, Eps[A, B] = Eps[B, A] = d(A, B). +
Lema 3.3 Dados um pontoA e uma linha poligonal [B1. . . Bn], n > 1,
εA,[B1...Bn] = max
i=1,...,nd(A, Bi).
Demonstra¸c˜ao: Como A(εA,[B1...Bn]) cont´em B1, . . . , Bn, isso implica que εA,[B1...Bn] ≥
max
i=1,...,nd(A, Bi). Uma vez que A(ε) ´e convexo, se P e Q s˜ao pontos tais que {P, Q} ⊆ A(ε),
ent˜ao [P Q] ⊆ A(ε). Conclui-se assim que εA,[B1...Bn]= max
i=1,...,nd(A, Bi).
A fun¸c˜ao Eps ter´a de determinar o m´aximo das normas dos vetores definidos pelo ponto correspondente ao primeiro argumento e pelos pontos que definem a linha poligonal dada como segundo argumento.
A Figura 3.3 apresenta trˆes exemplos em que a fun¸c˜ao Eps ´e invocada com um ponto como primeiro argumento e com o segundo argumento sendo uma linha poligonal definida por dois, trˆes e quatro pontos.
A =H0, 0L
B1=H-2, -2L
B2=H-1, 1L
¶A,@B1B2D= 2 2
(a) Ponto e linha poligonal for- mada por dois pontos.
A =H0, 0L B1=H-1, 1L B2=H-1, -1L B3 = H2 ,0 L ¶A,@B1B2B3D= 2
(b) Ponto e linha poligonal for- mada por trˆes pontos.
A =H0, 0L B1=H-1, 1L B2=H-1, -1L B3 = H2 ,0 L B4=H2, -2L ¶A,@B1º B4D= 2 2
(c) Ponto e linha poligonal for- mada por quatro pontos.
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 32
Analisemos agora a situa¸c˜ao inversa, ou seja, considerando como primeiro argumento uma linha poligonal e como segundo argumento um ponto.
Lema 3.4 Dados uma linha poligonal[A1. . . An], n > 1, e um ponto B,
ε[A1...An],B = min
i=1,...,n−1d(B, [AiAi+1]).
Demonstra¸c˜ao: Usando o Lema 3.1 com P = B e X = [A1. . . An] conclui-se que
ε[A1...An],B = d B, [A1. . . An] = min
i=1,...,n−1d B, [AiAi+1].
Para tratar este caso foram definidas duas instˆancias da fun¸c˜ao Eps, separando a si- tua¸c˜ao em que a linha poligonal ´e definida por dois pontos, ou seja, ´e um segmento de reta, da situa¸c˜ao em que a linha poligonal ´e definida por trˆes ou mais pontos. No primeiro caso a fun¸c˜ao Eps determina a distˆancia do ponto ao segmento de reta, situa¸c˜ao exemplificada na Figura3.4. Na outra situa¸c˜ao, considerando uma linha poligonal definida por n pontos, com n ≥ 3, a fun¸c˜ao Eps invoca n − 1 vezes a instˆancia anteriormente referida de Eps, de acordo com o Lema 3.4 e extrai o m´ınimo dos n − 1 valores obtidos. Esta situa¸c˜ao ´e exemplificada na Figura 3.5. A1=H-2, -1L A2= 1 2, -1 B =H0, 0L ¶@A1A2D,B= 1
(a) A distˆancia de B a [A1A2] ´e
realizada num ponto pertencente ao p´e da perpendicular.
A1=H-2, 0L A2=H0, 0L
B =H1, 1L
¶@A1A2D,B= 2
(b) A distˆancia de B a [A1A2]
´e realizada num dos extremos do segmento de reta.
Figura 3.4: Exemplos de aplica¸c˜ao da fun¸c˜ao Eps [seg,pt]. +
Considere-se agora uma situa¸c˜ao em que nenhum dos argumentos se reduz a um ponto. Lema 3.5 Dados um segmento de reta [A1A2] e uma linha poligonal [B1. . . Bn],
ε[A1A2],[B1...Bn] = max
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 33 A1=H-1, 1L A2=H-1, -1L A3=H1, 0L B =H-2, -2L ¶@A1A2A3D,B= 2
(a) O ponto B pertence `a salsicha dos dois segmentos de reta que formam a linha poligonal.
A1=H-1, 1L A2=H-1, -1L A3=H1, 0L B =H1, -1L ¶@A1A2A3D,B= 2 5
(b) O ponto B pertence `a salsicha de [A2A3]. A1=H-2, 1L A2=H-1, -1L A3=H1, 0L A4 = H2 ,- 2L B =H-1, 0L ¶@A1º A4D,B= 1 5
(c) O ponto B pertence `a salsicha de [A1A2].
Figura 3.5: Exemplos de aplica¸c˜ao da fun¸c˜ao Eps [lp,pt]. +
Demonstra¸c˜ao: Seja ε = max
i=1,...,nd(Bi, [A1A2]). Como
B1, . . . , Bn ∈ [A1A2](ε[A1A2],[B1...Bn]),
tem-se que ε[A1A2],[B1...Bn]≥ ε.
Por outro lado, como [A1A2](ε) ´e convexo, cont´em [BiBj], i, j = 1, . . . , n. Em parti-
cular[B1. . . Bn] ⊆ [A1A2](ε), logo ε[A1A2],[B1...Bn] ≤ ε.
Conclui-se assim que ε[A1A2],[B1...Bn]= ε.
Observando, de acordo com o Lema 3.4, que d(Bi, [A1A2]) = ε[A1A2],Bi, recorrendo a
uma instˆancia anterior, a fun¸c˜ao Eps calcula o m´aximo dos ε[A1A2],Bi, i = 1, . . . , n.
Na Figura 3.6 apresentam-se dois exemplos da situa¸c˜ao acabada de descrever.
Face `a sequˆencia dos lemas seria natural agora apresentar um resultado que permitisse definir um algoritmo para a constru¸c˜ao de Eps quando o primeiro argumento ´e uma linha poligonal e o segundo ´e um segmento de reta ou at´e uma linha poligonal. O pr´oximo lema vai nesse sentido, mas apenas considera uma situa¸c˜ao particular.
Lema 3.6 Dados uma linha poligonal [A1A2A3] e um segmento de reta [B1B2], designe-
mos porE o conjunto dos pontos equidistantes de [A1A2] e [A2A3], i.e.,
E =P ∈ R2 : d(P, [A
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 34 A1=H0, 1L A2= 1, 1 2 B 1 = H- 1, 1L B2=H-1, -1L B3=H1, 0L ¶@A1A2D,@B1B2B3D= 5
(a) Linha poligonal formada por dois segmentos de reta.
A1 = H- 1, 1L A2 = 0, 1 2 B 1 = H- 2, 1L B2=H-1, -1L B3 = H1 ,1 L B4 = 3 ,- 2 1 2 ¶@A1A2D,@B1º B4D= 13 2
(b) Linha poligonal formada por trˆes segmentos de reta.
Figura 3.6: Exemplos de aplica¸c˜ao da fun¸c˜ao Eps [seg,lp]. + 1. Se [B1B2] ∩ E = ∅ ent˜ao,
ε[A1A2A3],[B1B2]= min
i=1,2ε[AiAi+1],[B1B2].
2. Se [B1B2] ∩ E 6= ∅, designando por B3 um ponto de [B1B2] ∩ E, ent˜ao,
ε[A1A2A3],[B1B2]= max
i=1,2,3ε[A1A2A3],Bi.
Demonstra¸c˜ao: Seja ε = ε[A1A2A3],[B1B2].
1. Considere-se a situa¸c˜ao em que [B1B2] ∩ E = ∅.
Observando que [A1A2A3](ε) = [A1A2](ε) ∪ [A2A3](ε), ´e simples concluir que ε ≤
min
i=1,2ε[AiAi+1],[B1B2]. Suponhamos ent˜ao que
ε < min
i=1,2ε[AiAi+1],[B1B2]. (3.1)
Vejamos que existe B3 ∈ [B1B2] tal que d(B3, [A1A2]) ≤ ε < d(B3, [A2A3]).
Com efeito, existe um ponto em [B1B2] que est´a em [A1A2](ε) mas que n˜ao est´a em
[A2A3](ε) pois, caso contr´ario, [A1A2](ε) ⊇ [B1B2], o que implicaria que ε[A1A2],[B1B2]≤
ε, contrariando a hip´otese (3.1).
Analogamente se conclui que existe um ponto B4 ∈ [B1B2] tal que d(B4, [A2A3]) ≤
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 35
A fun¸c˜ao,
Φ : [B3B4] −→ R
B 7−→ d(B, [A1A2]) − d(B, [A2A3])
´
e cont´ınua e Φ(B3) < 0 < Φ(B4), logo existe B ∈ ]B3B4[ tal que Φ(B) = 0, i.e.,
B ∈ E, o que entra em contradi¸c˜ao com o facto de [B1B2] ∩ E = ∅. Conclui-se
assim que, se [B1B2] ∩ E = ∅, ent˜ao
ε[A1A2A3],[B1B2]= min
i=1,2ε[AiAi+1],[B1B2].
2. Seja B3 ∈ [B1B2] ∩ E, denotemos δi = d Bi, [A1A2A3], i = 1, 2, 3, e seja δ =
max
i=1,2,3δi. Vejamos que
∀ i ∈ {1, 2} ∃ j ∈ {1, 2} [BiB3] ⊆ [AjAj+1](δ). (3.2)
Com efeito, observando que δ ≥ δ3, tem-se que B3 ∈ [AjAj+1](δ), j = 1, 2 .
Fixemos i ∈ {1, 2}. Como δi ≤ δ, tem-se que Bi ∈ [A1A2A3](δ), logo Bi ∈
[AjAj+1](δ), para algum j ∈ {1, 2}. Usando o facto de [AjAj+1](δ) ser convexo,
conclui-se que[BiB3] ⊆ [AjAj+1](δ), donde se deduz (3.2), o que implica queε ≤ δ.
Por outro lado ´e imediato verificar queε ≥ δ. Obt´em-se assim que, se [B1B2]∩E 6= ∅
e sendo B3 um ponto de[B1B2] ∩ E, ε[A1A2A3],[B1B2]= max
i=1,2,3ε[A1A2A3],Bi.
Para efeitos do c´alculo de ε[A1A2A3],[B1B2], na sequˆencia do Lema3.6, ´e fundamental a
caracteriza¸c˜ao da regi˜ao de equidistˆancia E. Considerando trˆes pontos n˜ao colineares A1,
A2eA3, comecemos por representar as bandas abertas formadas pelos pontos cuja distˆancia
a cada um dos segmentos de reta [A1A2] e [A2A3] ´e realizada no p´e da perpendicular (ver
Figura 3.7(a)).
Com base nas bandas representadas, consideremos as regi˜oes R1 a R6 identificadas na
Figura 3.7(b).
A distˆancia de qualquer ponto de R1 aos segmentos de reta [A1A2] ou [A2A3] ´e a
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 36
A2 A1
A3
(a) Conjunto dos pontos em que a distˆancia aos segmentos de reta [A1A2]
ou [A2A3] se realiza no p´e da perpendi- cular. R4 R6 R3 R2 R1 R5 A2 A1 A3
(b) Regi˜oes de pontos R1a R6.
E1 R4 R6 R3 R2 R1 R5 A2 A1 A3
(c) Pontos de equidistˆancia pertencentes `
a bissetriz do ˆangulo ∠A1A2A3.
E1 E2 R4 R6 R3 R2 R1 R5 A2 A1 A3
(d) Pontos de equidistˆancia pertencentes ao arco de par´abola E1E2.
E1 E2 R4 R6 R3 R2 R1 R5 A2 A1 A3
(e) Pontos de equidistˆancia pertencentes `
a mediatriz do segmento de reta [A1A3].
E1 E2 R4 R6 R3 R2 R1 R5 A2 A1 A3
(f) Conjunto de pontos equidistˆancia.
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 37
R1, os pontos equidistantes de [A1A2] e [A2A3] s˜ao os pontos equidistantes das retas
suporte, i.e., s˜ao os pontos que pertencem `a bissetriz do ˆangulo ∠A1A2A3 e `a regi˜ao R1
(ver Figura3.7(c)).
A distˆancia de qualquer ponto de R2 a [A1A2] coincide com a distˆancia desse ponto a
A1 e a distˆancia de qualquer ponto deR2 a[A2A3] ´e determinada pelo p´e da perpendicular
`a reta suporte de [A2A3]. Tem-se ent˜ao que os pontos de R2 equidistantes de [A1A2] e
[A2A3] s˜ao os pontos equidistantes de A1 e da reta suporte de[A2A3], o que define um arco
de par´abola cujo foco ´e A1 e cuja diretriz ´e a reta suporte de [A2A3] (ver Figura 3.7(d)).
A distˆancia de qualquer ponto de R3 a [A1A2] ´e igual `a distˆancia desse ponto a A1 e a
distˆancia de qualquer ponto deR3a[A2A3] ´e igual `a distˆancia desse ponto a A3. Conclui-se
ent˜ao que os pontos de R3 equidistantes de [A1A2] e [A2A3] s˜ao os pontos equidistantes
de dois pontos, pelo que se trata dos pontos da mediatriz do segmento de reta[A1A3] que
pertencem a R3 (ver Figura 3.7(e)).
A distˆancia de qualquer ponto de R4 a [A1A2] e a [A2A3] coincide com a distˆancia
desse ponto a A2, pelo que todos os pontos do cone designado por R4 s˜ao equidistantes
de[A1A2] e de [A2A3].
Relativamente aos pontos pertencentes a R5, qualquer ponto desta regi˜ao encontra-se
mais pr´oximo de [A1A2] do que de [A2A3], pelo que, n˜ao existem, nesta regi˜ao, pontos
equidistantes de [A1A2] e de [A2A3]. Como qualquer ponto de R6 est´a mais pr´oximo
de [A2A3] do que de [A1A2], conclu´ı-se ent˜ao que tamb´em n˜ao existem, em R6, pontos
equidistantes de [A1A2] e de [A2A3].
Fica assim caracterizada a regi˜ao de equidistˆancia E (ver Figura3.7(f)).
Observe-se que, se os pontosA1,A2 eA3 forem colineares, estes definem um segmento
de reta e, nesse caso, a regi˜ao de equidistˆancia ser´a formada pela reta perpendicular a esse segmento de reta que passa porA2.4
No caso deA1A2 = A2A3 e os pontos A1,A2 eA3 n˜ao serem colineares, a bissetriz do
ˆangulo ∠A1A2A3 est´a contida na mediatriz do segmento de reta [A1A3] e, nesta situa¸c˜ao,
o arco de par´abola degenera num ponto.
Denotaremos por E a regi˜ao de equidistˆancia. Denotaremos ainda por CE a regi˜ao de
4De facto, se A
1∈ [A2A3] ou A3∈ [A1A2], ent˜ao a regi˜ao de equidistˆancia ´e a banda limitada pelas
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 38
E correspondente ao cone de equidistˆancia (regi˜ao R4 na Figura 3.7) e por ΓE a curva
de equidistˆancia correspondente `a uni˜ao do segmento de reta, do arco de par´abola e da semirreta que constituem a regi˜ao de equidistˆancia correspondentes `as regi˜oes R1, R2 e
R3, respetivamente, identificadas na Figura 3.7. Os pontos que limitam o arco de par´abola
ser˜ao denotados porE1 e E2, tal como na Figura 3.7.
Para exemplificar a regi˜ao de equidistˆancia elaborou-se uma pequena anima¸c˜ao, embe- bida na Figura 3.8, onde se pode observar a evolu¸c˜ao dessa regi˜ao quando se movem os pontos que definem os extremos dos segmentos de reta.
Eps1 0
Figura 3.8: Regi˜ao de equidistˆancia. +
Na constru¸c˜ao da curva de equidistˆancia, a representa¸c˜ao do arco de par´abola limitado pelos pontos E1 e E2 ´e feita com recurso a uma curva de B´ezier quadr´atica, usando trˆes
pontos de controlo: os extremos do arco de par´abola e um terceiro ponto correspondente `a interse¸c˜ao das retas tangentes `a par´abola nos pontosE1 eE2. Esse ponto de interse¸c˜ao,
corresponde `a interse¸c˜ao da bissetriz do ˆangulo ∠A1A2A3 e da mediatriz do segmento de
retaA1A3, como se pode concluir da proposi¸c˜ao seguinte.
Proposi¸c˜ao 3.7 Dados os pontos A1, A2 e A3, a curva de equidistˆancia de [A1A2] e
[A2A3], ΓE, ´e uma curva de classe C1.
Demonstra¸c˜ao: Designemos porθ a amplitude do ˆangulo ∠A1A2A3 e consideremos que
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 39 E1 E2 A1 A2 C1C2C3 A3 C4
Figura 3.9: Figura auxiliar `a demonstra¸c˜ao de queΓE ´e uma curva de classe C1.
pertence ao semieixo positivo das abcissas e queA1 tem ordenada 1, ou seja,A1 = (1, α),
A2 = (0, 0) e A3 = (β, 0), α, β ∈ R+ (ver Figura 3.9). Sejam E1 = (xE1, yE1) e
E2 = (xE2, yE2) as extremidades do arco de par´abola.
A curva de equidistˆancia ΓE, nesta situa¸c˜ao, corresponde ao gr´afico de uma fun¸c˜ao.
Provar que a curva ´e de classe C1 ´e provar que a fun¸c˜ao ´e deriv´avel em xE1 e em xE2.
A par´abola cujo foco ´e o ponto (1, α) e cuja diretriz ´e a reta y = 0 corresponde ao gr´afico da fun¸c˜ao y = (x − 1) 2 2α + α 2, (3.3) cuja derivada ´e y0 = x − 1 α . (3.4)
Como E1 ´e um ponto da bissetriz do ˆangulo ∠A1A2A3, A1A2 = A2C2 =
√
1 + α2 (ver
Figura 3.9), logo xE1 =
√
1 + α2. Por outro lado, comoE
1 pertence `a par´abola,
A1E1 = E1C2 ⇔ ( √ 1 + α2− 1)2+ (y E1 − α) 2 = y2 E1 ⇔ 1 + α2− 2√1 + α2+ 1 + y2 E1 − 2αyE1 + α 2 = y2 E1 ⇔ yE1 = 1 + α2−√1 + α2 α , logo E1 = √ 1 + α2,1+α2−√1+α2 α . O declive da reta A2E1 ´e dado por
yE1 xE1 = 1 + α 2−√1 + α2 α√1 + α2 = √ 1 + α2− 1 α . (3.5)
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 40
O declive da reta tangente `a par´abola em E1 ´e dado por
y0(xE1) = xE1 − 1 α = √ 1 + α2− 1 α . (3.6)
De (3.5) e (3.6) conclui-se que a fun¸c˜ao que representa a curva de equidistˆancia ´e deriv´avel em E1.
O declive da reta tangente `a par´abola em E2 ´e dado por
y0(β) = β − 1
α . (3.7)
Usando a semelhan¸ca de triˆangulos, 4[A3E2C3] ∼ 4[A3C4E2] ∼ 4[A3C1A1] (ver
Figura 3.9), conclui-se que o declive da reta C3E2 ´e dado por
E2A3 A3C3 = C4E2 C4A3 = A3C1 A1C1 = β − 1 α . (3.8)
De (3.7) e (3.8) resulta que a fun¸c˜ao que representa a curva de equidistˆancia ´e deriv´avel emE2.
De modo an´alogo se demonstra a derivabilidade da fun¸c˜ao que representa a curva de equidistˆancia em E1 e em E2 seθ ∈ [π2, π[ .
Proposi¸c˜ao 3.8 Sejam[A1A2A3] uma linha poligonal, [B1B2] um segmento de reta e seja
E o conjunto dos pontos equidistantes de [A1A2] e [A2A3].
Se]B1B2[ ∩ E ´e n˜ao vazio e n˜ao singular ent˜ao,
ε[A1A2A3],[B1B2] = min
i=1,2ε[AiAi+1],[B1B2],
i.e., apenas os extremos do segmento de reta [B1B2] s˜ao determinantes no c´alculo de
ε[A1A2A3],[B1B2].
Demonstra¸c˜ao: Recordemos queE = CE∪ ΓE. Vejamos que se]B1B2[ ∩ E ´e n˜ao vazio
e n˜ao singular ent˜ao existem dois pontos, B3, B4 ∈ ]B1B2[ tais que d(B3, [A1A2A3]) <
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 41
Se ]B1B2[ ∩ CE 6= ∅, ent˜ao existe uma infinidade de pontos pertencentes simultanea-
mente a ]B1B2[ e ao cone CE.
Consideremos P1 e P2 dois pontos distintos pertencentes a ]B1B2[ e ao cone de equi-
distˆancia. Se P1 e P2 pertencem ao mesmo arco de circunferˆencia de centro em A2 ent˜ao
P1 eP2 est˜ao `a mesma distˆancia de[A1A2A3]. Tomamos ent˜ao B3 = P1+P2 2 eB4 = P1 ou
B4 = P2. Se P1 e P2 n˜ao pertencem ao mesmo arco de circunferˆencia de centro em A2,
ent˜ao d(P1, A2) 6= d(P2, A2), bastando tomar B3 = P1 e B4 = P2, ou vice versa.
Se ]B1B2[ ∩ CE = ∅, consideremos uma fun¸c˜ao γ : [0, +∞[ −→ R2, injetiva, corres-
pondente a uma parametriza¸c˜ao cont´ınua da curva de equidistˆanciaΓE.
Consideremos a fun¸c˜ao
ψ : [0, +∞[ −→ R+0,
t 7−→ d(γ(t), [A1A2A3])
que ´e estritamente crescente.
Sejam P1 e P2 pertencentes a ]B1B2[ ∩ ΓE e sejam t1, t2 ∈ R+0 tais que P1 = γ(t1)
e P2 = γ(t2). Supondo, sem perda de generalidade, que t1 < t2, basta ent˜ao tomar
B3 = γ(t1) = P1 eB4 = γ(t2) = P2.
Fica ent˜ao justificado que, nas condi¸c˜oes indicadas, existem dois pontos B3, B4 ∈
]B1B2[ tais que d(B3, [A1A2A3]) < d(B4, [A1A2A3]).
Vejamos agora qued(B4, [A1A2A3]) ≤ max
i=1,2ε[A1A2A3],Bi.
Suponhamos que d(B4, [A1A2A3]) > max
i=1,2ε[A1A2A3],Bi. Como d(B4, [A1A2A3]) >
d(B3, [A1A2A3]) tem-se que d(B4, [A1A2A3]) > max
i=1,2,3ε[A1A2A3],Bi. Por outro lado, pelo
Lema3.6, sabemos que,
ε[A1A2A3],[B1B2]= max i=1,2,3ε[A1A2A3],Bi, portanto, d(B4, [A1A2A3]) ≤ max i=1,2ε[A1A2A3],Bi, o que ´e absurdo.
3.2 Caracteriza¸c˜ao da fun¸c˜ao Eps 42
Suponhamos agora que existe, eventualmente, um ponto B5 ∈ ]B1B2[ ∩ E tal que
d(B5, [A1A2A3]) > d(B4, [A1A2A3]).
Usando o racioc´ınio anterior e os mesmos argumentos, colocando B4 no lugar de B3 e B5
no lugar de B4, conclui-se que d(B5, [A1A2A3]) ≤ max
i=1,2ε[A1A2A3],Bi.
A Proposi¸c˜ao 3.8 vem justificar o facto do algoritmo da fun¸c˜ao Eps que determina o valorε[A1A2A3],[B1B2]desprezar a verifica¸c˜ao da interse¸c˜ao do segmento de reta[B1B2] com
o cone de equidistˆancia. Como ficou demonstrado, no caso da interse¸c˜ao de [B1B2] com a
regi˜ao de equidistˆancia se verificar em mais do que um ponto, os pontos relevantes para a sua determina¸c˜ao s˜ao os extremos do segmento de reta[B1B2]. Em termos computacionais
o esfor¸co seria bastante maior se a fun¸c˜ao Eps tivesse de verificar a interse¸c˜ao com o cone de equidistˆancia.
Na Figura3.10apresentam-se trˆes exemplos do c´alculo deε[A1A2A3],[B1B2]numa situa¸c˜ao
em que o ponto de interse¸c˜ao com a curva de equidistˆancia ´e quem determina o valor de ε, numa situa¸c˜ao em que o segmento de reta n˜ao interseta a regi˜ao de equidistˆancia e numa situa¸c˜ao em que h´a interse¸c˜ao entre o segmento de reta e o cone de equidistˆancia.
A1=H-1, 0L
A2=H0, 1L
A3=H1, 0L
B1=H-1, -1L B2=H1, -1L
¶@A1A2A3D,@B1B2D= 2
(a) O valor de ε ´e calculado usando um ponto que pertence `a curva de equidistˆancia ΓE.
A1=H-1, 0L A2=H0, 1L A3=H1, 1L B1=H-1, -1L B2= 0, - 1 2 ¶@A1A2A3D,@B1B2D= 3 2 2
(b) Situa¸c˜ao em que n˜ao existe interse¸c˜ao com a regi˜ao de equi- distˆancia E. A1=H-1, -1L A2=H0, 0L A3= 3 2, -1 B1 = - 1, 1 2 B2=H1, 1L ¶@A1A2A3D,@B1B2D= 5 13
(c) Situa¸c˜ao em que [B1B2] in-
terseta o cone de equidistˆancia CE.
Figura 3.10: Exemplos de aplica¸c˜ao da fun¸c˜ao Eps [lp,seg]. +
Na Figura3.11, na vers˜ao digital deste documento, apresenta-se uma anima¸c˜ao an´aloga `a que foi apresentada na Figura3.1, mas agora o c´alculo dos valores Eps1 e Eps2 ´e feito automaticamente e estes valores s˜ao atualizados sempre que se altera a posi¸c˜ao dos pontos,