Algoritmos de Otimização para Construção de Tesselações Centroidais de Voronoi

Arthur Gabriel de Santana
Orientador: Ernesto G. Birgin

Diagramas de Voronoi são particionamentos do Rⁿ formados por células definidas de acordo com a distância de cada ponto a certos pontos geradores. Tesselações Centroidais de Voronoi (TCVs) são um tipo particular de Diagrama de Voronoi que encontra diversas aplicações em áreas como Pesquisa Operacional, simulação e clustering. A construção de TCVs geralmente envolve métodos iterativos e pode ser interpretada como um problema de otimização. Neste trabalho, estudamos propriedades básicas de Diagramas de Voronoi e TCVs, além de algoritmos para a construção destas estruturas.