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