Título
[en] AN ALGORITHM FOR THE COMPUTATION OF SOME DISTANCE FUNCTIONS BETWEEN CONVEX POLYGONS
Título
[pt] UM ALGORITMO LINEAR PARA O CÁLCULO DE ALGUMAS FUNÇÕES DISTÂNCIA ENTRE POLÍGONOS CONVEXOS
Autor
[pt] SERGIO LIFSCHITZ
Vocabulário
[pt] POLIGONO CONVEXO
Vocabulário
[pt] ALGORITMO LINEAR
Vocabulário
[en] CONVEX POLYGON
Vocabulário
[en] LINEAR ALGORITHM
Resumo
[pt] Apresenta-se nesta dissertação um novo algoritmo para o
cálculo de algumas funções distância entre polígonos
convexos, no caso geral em que os polígonos podem se
interseptar, cuja complexidade linear de pior caso é melhor
do que a dos algoritmos até então conhecidos na literatura.
O algoritmo é baseado em um algoritmo de complexidade
linear originalmente proposto para determinação da
distância de Hausdorff entre polígonos convexos disjuntos e
utiliza como sua principal componente um algoritmo linear
para o cálculo da interseção entre polígonos convexos. A
motivação para o estudo de algoritmos eficientes para este
problema de cálculo de distâncias decorre de aplicações em
reconhecimento de formas e superposição ótima de contornos.
Resultados computacionais também são apresentados.
Resumo
[en] We present in this dissertation a new algorithm for the
computation of some distance functions between convex
polygons, in the general case where they can intersect,
whose worst case time complexity is better than of the
previously known algorithms. The algorthm is based on an
algorithm originally proposed for the computation of the
Hausdorff distance between disjoint polygons and uses as
its main component a linear time algorithm for finding the
intersection of convex polygons. The motivation for the
study of efficient algorithms for this distance computation
problem comes from applications in pattern recognition and
contour fitting. Computatioal results are also presented.
Orientador(es)
CELSO DA CRUZ CARNEIRO RIBEIRO
Banca
REINALDO CASTRO SOUZA
Banca
MARCELO GATTASS
Banca
NELSON MACULAN FILHO
Banca
ANTONIO ALBERTO FERNANDES DE OLIVEIRA
Banca
RONALDO CESAR MARINHO PERSIANO
Catalogação
2006-12-28
Apresentação
1990-08-09
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9412@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9412@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.9412
Arquivos do conteúdo
NA ÍNTEGRA PDF