Algoritmo discreto para determinação do cı́rculo máximo
inscrito num polı́gono ∗
Mercio Botelho Faria†,
Marcelo Firer‡,
Instituto de Matemática, Estatı́stica e Ciência da Computação, IMECC, UNICAMP,
Caixa Postal: 6065 CEP - 13083-859, Campinas, SP
E-mail: [email protected],
[email protected]
Dado um polı́gono convexo P , buscamos algo2) A cada ponto pijkl encontramos os ponritmo discreto para determinação do maior cı́rculo
tos Mtijkl ∈ γt (t = i, j, k, l) que satinscrito em P . O algoritmo elaborado baseia-se
isfazem d (pijkl , γt ) =
inf d (pijkl , z) =
z∈γt
³
´
em fatos relativamente elementares e se inspira no
d pijkl , Mtijkl . Descartamos pijkl se Mt ∈
/ τt ,
trabalho de Karkasis e Karagiorgis ([1]), que descreveram algoritmo para o caso de polı́gono no
para algum t ∈ {i, j, k, l} ;
plano euclidiano. Diferentemente do algoritmo de
3) Escolheremos dentre os pontos
[1], a proposta aqui apresentada é válida para todas
³ pijkl da etapa
´
as superfı́cies de curvatura constante e é essencialanterior os que satisfazem d pijkl , Mjijkl =
³
´
mente discreto e com complexidade baixa, de ordem
ijkl
d
p
,
M
;
4
ijkl
k
n , onde n é o número de arestas do polı́gono.
³
´
³
´
Seja P um polı́gono com vértices {v1 , v2 , ..., vn } e
4) Seja r := d pijkl , Mjijkl = d pijkl , Mkijkl .
arestas {τ1 , τ2 , ..., τn } , com τi unindo os vértices vi
e vi+1 (módulo n). Denotaremos por {γ1 , γ2 , ..., γn }
Verificamos se r ≤ d (pijkl , τt ) , onde t ∈
o conjunto das geodésicas suportes, isto é, cada γi
{1, 2, ..., n} ;
é a geodésica que contém a aresta τi e seja ∂P a
5) Dentre todos os pontos encontrados no passo
fronteira de P . Definimos o cı́rculo máximo inscrito
quatro, terminamos com a escolha do ponto
(CMI) C (c, r) do polı́gono P como sendo o cı́rculo
pijkl com maior raio r.
inscrito em P de raio máximo.
O algoritmo proposto baseia-se em dois fatos elEste algoritmo é implementado no programa
ementares: a) Dado um polı́gono P , todo CMI tem
Mathematica,
que gerou as ilustrações abaixo (casos
pelo menos três pontos de tangência em comum
euclidiano
e
hiperbólico).
com a ∂P ; b) Uma bissetriz de um ângulo é uma
geodésica equidistande das geodésicas que determiRaio
2
Raio
nam o ângulo.
A partir destes dois fatos, é possı́vel demonstrar
1
Centro
a seguinte proposição:
Proposição 0.1 Seja P um polı́gono convexo.
Então C (c, r) o cı́rculo máximo inscrito (CMI) em
P tem seu seu centro c sobre a interseção de bissetrizes de geodésicas suporte de P .
Deste resultado, temos que para encontrar o
CMI em um polı́gono convexo devemos analisar somente os pontos de interseção das bissetrizes das
geodésicas suportes.
Para determinarmos os centros dos CMI, consideramos o polı́gono P com vértices {v1 , v2 , ..., vn } e
procedemos do seguinte modo:
-2
-1
1
Centro
2
3
-1
-2
4
5
-2
0
2
4
6
Plano Hiperbólico
Referências
[1] Karkazis, J. & Karagiorgis, P. A method to locate the maximum circle(s) incribed in a polygon. Belgian Journal of Operations
1) Determinamos todos os pontos de interseção
Research, Statistics and Computer Science,
pijkl correspondentes as interseções das bis1986, vol. 26, n. 3, pág. 1-36.
setrizes βij e βkl , onde as bissetrizes {βij , βkl }
das geodésicas suportes {{γi , γj } , {γk , γl }};
[2] Beardon, Alan F. The geometry of discrete
∗ Apoio financeiro da FAPESP
groups. Springer-Verlag, New York, 1983.
† Aluno
de Doutorado em Matemática
‡ Orientador