Fórum

Eu estava aqui dando uma olhada no algoritmo dado em aula para cálculo de fecho convexo e fiquei seriamente intrigado quanto à utilidade dele.

Se utilizarmos um algoritmo geométrico (com o algoritmo de Graham) para o cálculo exato do fecho convexo, o consumo de tempo será algo como Teta(n*lg), sendo n o número de pontos da imagem. Como talvez seja necessário, em seguida, realizar um preenchimento, vou acrescentar um tempo Teta(n*h) ao que já citei, sendo h o número de dilatações necessárias para concluir o preenchimento (estou supondo que o tamanho do elemento estruturante é constante, uma vez que isto não afeta a comparação entre os dois métodos que estou considerando). Ou seja: minha análise pedreira nos dá um tempo Teta(n*(lg + h)).

Com o método dado em aula, temos algo como Teta(n*b), sendo b o número de transformações hit-or-miss necessárias. Esse número b não me parece muito diferente do h ali em cima (sem contar que aqui temos quatro elementos estruturantes), assim como não me parece assintoticamente inferior a lg (eu chutaria raiz para ele).

Enfim, acho que analisar esses métodos de forma cuidadosa exigiria algumas formalizações trabalhosas. Mas, pelo menos à primeira vista, não consigo enxergar uma desvantagem no consumo de tempo de um algoritmo geométrico que justifique a sua substituição por um algoritmo, digamos, "de aproximação".

O Gonzalez comenta algo sobre o assunto (não estou com o livro)?