Menor Círculo Envolvente
Eraldo Luís Rezende Fernandes ([email protected])
Michel Alain Quintana Truyenque ([email protected])
Menor Círculo Envolvente
• Minimal Enclosing Circle (MCE)
• Dados n pontos no plano, encontrar o
círculo de menor raio que contenha todos
os pontos
• Pode ser estendido para espaço de dimensão
d (Minimal Enclosing Ball)
Aplicações
• Planejamento de localização
• Rotação de polígonos
• Problemas que envolvem testes de
proximidade com conjuntos de pontos
• Aproximação para a maior distância entre
dois pontos de um conjunto de pontos
Algoritmos
• Força bruta: O(n3)
• Algoritmo iterativo: O(n2)
• Algoritmo aleatório baseado em
Programação Linear (Welzl, 1991): O(n)
Algoritmo Iterativo Quadrático
• Passo 1: Defina um círculo suficientemente grande
que envolva todos os pontos (centro arbitrário)
Algoritmo Iterativo Quadrático
• Passo 2: Encontre o ponto A que esteja mais
distante do centro do círculo anterior e redefina o
círculo passando por A
Algoritmo Iterativo Quadrático
• Passo 3: Diminua o círculo mantendo o ponto A na
sua fronteira e movendo o seu centro em direção
ao ponto A até tocar outro ponto B do conjunto
Algoritmo Iterativo Quadrático
• Passo 4:
• Tem-se agora um círculo passando por dois ou mais
pontos
• Se estes pontos definem um arco maior do que  então
o círculo pode ser diminuído ainda mais (caso
contrário, o MEC é o círculo atual)
• Sejam D e E os dois pontos que definem o arco maior
que . Diminuir o raio do círculo mantendo-o em
contato com os pontos D e E até que:
• O diâmetro do círculo seja o segmento DE; ou
• O círculo toque um terceiro ponto
Algoritmo Iterativo Quadrático
• Passo 4:
Algoritmo Iterativo Quadrático
• Passo 4:
• Se um círculo com diâmetro DE é encontrado então
este é o MEC
• Se o círculo toca um terceiro ponto então repete-se o
passo 4
Algoritmo Iterativo Quadrático
• Passo 4: (novamente)
Algoritmo Iterativo Quadrático
Algoritmo Aleatório de Welzl
• Proposto em 1991 por Emo Welzl
• Inspirado no algoritmo aleatório de
programação linear
• Também é incremental, porém, Welzl o
propos em forma de um procedimento
recursivo
Algoritmo Aleatório de Welzl
• Calcula o MEC para n pontos de forma
incremental. Inicia construindo o MEC para dois
(ou três) pontos, e segue incluindo os pontos
seguintes um após o outro sempre mantendo o
MEC do conjunto considerado
• Teoremas necessários:
• Seja md(P) o disco definido pelo MEC do conjunto de
pontos P
• Para qualquer P, md(P) é bem definido (é único)
• São necessários no máximo 3 pontos para definir
md(P), ou seja, existe S  P tal que |S| <= 3 e md(S) =
md(P)
Algoritmo Aleatório de Welzl
• Seja P = {p1,p2,...,pn} o conjunto de entrada e
suponha que Di = md({p1,p2,...,pi}) já foi calculado
• Se pi+1 Di então Di+1 = Di
• Se pi+1 Di então Di+1 é o disco definido pelo
MEC dos pontos {p1,p2,...,pi} e que passa por pi+1.
Neste caso o MEC dos pontos é calculado pelo
procedimento b_mce({p1,p2,...,pi}, pi+1)
Algoritmo Aleatório de Welzl
função mce(P)
se P = Ø então
D := Ø;
senão
escolhe p  P aleatoriamente
D := mce(P - {p});
se p  D então probabilidade 3/n
D := b_mce(P - {p}, p);
retorna D;
fim
Algoritmo Aleatório de Welzl
• Dados dois conjuntos P e R de pontos no plano,
seja b_md(P, R) o menor disco que contenha todos
os pontos de P e possua todos os pontos de R na
sua fronteira
• Se b_md(P, R) existe então ele é bem definido
• Se p  b_md(P – {p}, R) então p está na fronteira
de b_md(P, R), dado que ele existe, ou seja,
b_md(P, R) = b_md(P – {p}, R  {p})
• Se b_md(P, R) existe então existe um conjunto S
de no máximo max{0, |R|} tal que b_md(P, R) =
b_md(S, R)
Algoritmo Aleatório de Welzl
função b_mce(P, R)
se P = Ø ou |R| = 3 então
D := b_md(Ø, R);
senão
escolhe p  P aleatoriamente
D := b_mce(P - {p});
se p  D então probabilidade 3/n
D := b_mce(P - {p}, R  {p});
retorna D;
fim
Algoritmo Aleatório de Welzl
função mce(P)
b_mce(P, Ø);
fim
Menor Círculo Envolvente
http://www.inf.puc-rio.br/~eraldoluis/mec