~
A TRIANGULACAO
DOS POLIGONOS
,
Luiz Felipe Araujo Mod, Valério Ramos Batista
CMCC, Universidade Federal do ABC
Rua Sta. Adélia, 166 - Santo André - SP
[email protected], [email protected]
1
AGRADECIMENTO
Teorema 4.3 (Existência e Unicidade das Perpendiculares - TEUP). Sejam r e X, então ∃ !s tal que
Este trabalho foi financiando por Bolsa FAPESP de Iniciação Cientı́fica, processo 09/07882-3.
2
X ∈ s ⊥ r.
Teorema 4.4. Seja r e B ∈
/ r, então ∃ s//r com B ∈ s.
RESUMO
Intuitivamente, todo polı́gono é triangularizável. No caso euclidiano, geômetras do passado apresentaram suas provas, mas
Lema 4.1. Dados n pontos, ∃ r tal que todos estão do mesmo lado de r.
elas aparentemente carecem de mais explicações (vide referências). A literatura é de fato antiga, pois a Geometria Plana
Dem: Vale para n = 1, pois ∃ s tal que P 6∈ s. Suponha que vale para m pontos. Dado n = m + 1, tome s tal que
Axiomática é atualmente uma disciplina de graduação, e não uma área de pesquisa como foi no passado. Refazemos aqui
˙ ′ pelo Teorema 4.1. Se Pn ∈ L′, tome t//s com Pn ∈ t, que existe
P1, . . . , Pm estão do mesmo lado L de s, Π \ s = L∪L
uma demonstração em linguagem moderna e sem o Postulado das Paralelas. É um trabalho inovador pois a literatura
˙ ′, e como s ∩ t = ∅, podemos dizer que s ⊂ H. Do Teorema 4.2, temos que P1, . . . , Pm
pelo Teorema 4.4. Seja Π \ t = H∪H
clássica define triangulação de um modo fraco, em contraste com a nossa definição, muito mais exigente. Além disso, nossa
estão do mesmo lado H de t, e escolhemos Q ∈ H′, que não é vazio pelo Teorema 4.1. Tome r//t com Q ∈ r, donde
demonstração foi implementada em Matlab, e todo seu código-fonte será disponibilizado para fins didáticos.
r ⊂ H′. Assim, teremos P1, . . . , Pn do mesmo lado que r. Caso Pn ∈ s, aplique o mesmo procedimento para t = s.
3
5
INTRODUÇÃO
RESULTADO PRINCIPAL
Teorema 5.1. Todo polı́gono admite uma triangulação.
Dado um polı́gono P com vértices V1, . . . , Vn, dizemos que T é uma triangulação de P quando:
(a) ∀ i ∃ ∆ ∈ T tal que Vi é vértice de ∆;
˙ ′ tal que V1, . . . , Vn ∈ L.
Dem: Seja P um polı́gono com vértices {V1, . . . , Vn}. Do Lema 4.1, tome r com Π \ r = L∪L
(b) ∀ ∆, ∆′ ∈ T , ∆ ∩ ∆′ é um lado ou vértice comum, ou vazia;
Do TEUP, sejam Q1, . . . , Qn ∈ r tais que ViQi ⊥ r, ∀ i. Então ∃ AB =min{ViQi, i = 1, . . . , n}. A menos de reindexar,
(c) ∀ ∆ ∈ T , seus vértices pertencem a {V1, . . . , Vn}.
supomos V2Q2 ≡ AB. Seja s ⊥ V2Q2 com V2 ∈ s e I := {i 6= 1, 3|Vi ∈ Int(∆V1V2V3) ∪ V1V3}. Caso I 6= ∅, tome
←→
←→
CD =max{dist(Vi, V1V3 ), i ∈ I}. Seja j ∈ I tal que dist(Vj , V1V3 ) = CD.
Neste trabalho, provamos que todo polı́gono é triangularizável, desde que satisfaça o critério da maior distância, expli-
O próximo passo da demonstração leva em conta que V2Vj ∩ P = {V2, Vj }. Sempre que isso ocorrer, diremos que o plano
cado durante a demonstração. Nela mencionamos resultados clássicos de Geometria que listamos na Parte 4.
Na Figura 1 de nosso programa triang.m, vemos que o usuário pode otimizar a triangulação (caso euclidiano). A Figura
2 é do programa htriang.m e mostra a execução do caso hiperbólico (modelo do semi-plano superior, eixo vertical de
(do polı́gono) verifica o critério da maior distância. Isto é claro no plano Euclidiano, onde vale o Axioma das Paralelas. No plano hiperbólico, usamos o fato de que todas as transformações de Möbius (incluindo as conjugadas) de B1(0)
em B1(0) são isometrias. Então, sem perda de generalidade podemos supor que V1,3 ∈ (−1, 1) e V2 ∈ i(0, 1) (vide Figura 3).
logaritmandos).
100
100
90
90
80
80
V2
Vj
70
70
V1
60
60
50
50
40
40
30
30
20
20
10
10
0
0
V3
Figura 03: O critério da “maior distância”.
Na Figura 3, as linhas pontilhadas são as eqüidistantes. Podemos folhear toda a região entre elas por uma famı́lia de
0
10
20
30
40
50
60
70
80
90
100
0
10
20
30
40
50
60
70
80
90
100
eqüidistantes. Cada ponto do segmento geodésico ligando V2 a Vj cruza exatamente um membro da famı́lia. Ou seja, ele
−→
está inteiramente entre as eqüidistantes de V2 e Vj . Isto é garantido pela Proposição 4.1, que implica V2Vj ∩ V1V3 = {X}.
100
100
90
90
80
80
Assim, definimos P′ e P′′, onde P′ tem vértices V1, V2 e Vk , k = j, . . . , n, enquanto que P′′ tem vértices V2, V3 e Vk ,
70
70
k = 4, . . . , j. Cada novo polı́gono tem um número de lados menor ou igual a n − 1. Agora, se I = ∅ definimos P′
60
60
com vértices V1 e Vi, i = 3, . . . , n, e o primeiro elemento da triangulação é ∆V1V2V3. Neste caso, P′′ = ∅. Repetimos o
50
50
procedimento descrito nestes parágrafos até esgotarmos todos os passos.
40
40
30
30
20
20
10
10
0
0
Então, V2Vj ∩ P = {V2, Vj }, pois do contrário Vj não seria o vértice de maior distância.
OBSEVAÇÃO IMPORTANTE: Note que o critério para a obtenção de Vj não pode ser o de menor distância a V2,
−→
−→
nem o que faz menor ângulo com V2V1 ou V2V3 , mesmo no plano Euclidiano, como mostram as Figuras 4 e 5. No primeiro
caso, já sabı́amos que seria um critério falho, donde não foi implementado em Matlab. No segundo caso, a implementação
0
10
20
30
40
50
60
70
80
90
100
0
10
20
30
40
50
60
70
80
90
100
em Matlab indicou nosso erro de raciocı́nio, o que levou a rever critérios, demonstração e implementação. Isso mostra a
importância do acompanhamento numérico de uma demonstração, sempre que possı́vel.
Figura 01: Triangulação sendo otimizada.
V2
100
100
90
90
80
80
70
70
60
60
50
50
40
40
75
30
30
70
20
20
65
10
10
60
V3
V1
Figura 04: Falha no critério da “menor distância”.
0
0
10
20
30
40
50
60
70
80
90
100
0
55
0
10
20
30
40
50
60
70
80
90
100
50
45
Figura 02: Triangulação hiperbólica.
40
35
4
RESULTADOS CLÁSSICOS
30
50
op
oposto S (r, A) := B.
60
65
70
75
80
85
90
95
Figura 05: Falha no critério do “menor ângulo”.
˙
Teorema 4.1. Dada a reta r no plano Π, tem-se Π \ r = A∪B,
onde A, B são convexos e não vazios.
Definição 4.1. De acordo com o Teorema 4.1, o semi-espaço determinado por r e A 6∈ r é S(r, A) := A e seu
55
Referências
[1] Forder, H.G. - The Foundations of Euclidean Geometry, Cambridge Univ. Press: Cambridge, (1927).
→
→
Teorema 4.2. Seja s uma semi-reta não contida em r mas com origem O ∈ r. Então, ∀ P ∈ ( s \ r) ⇒
→ −→
s = OP ⊂ (S(r, P ) ∪ {O}).
[2] Hartshorne, R. - Geometry: Euclid and beyond, Springer: New York, (2000).
[3] Hilbert, D. - Foundations of Geometry, Open Court Pub. Co: Chicago, (1912).
[4] Legendre, A.-M. - Eléments de Géometrie, Lib. Firmin Didot: Paris, (1852).
−→
b ), temos P L ∩ KG
= {R}, com P − R − L.
Proposição 4.1. Dado G ∈ Int(LKP
APOIOS:
[5] Pasch - Vorlesungen über neuere Geometrie, Teubner: Leipzig, (1882).