Salve, Os resultados abaixo, descritos pelo Yoshi, mostram que o consumo de tempo esperado (sob certas hipóteses) do algoritmo embrulho-para-presente é proporcional a n \log n.
-- BEGIN included message
- Subject: Conv{X_1,...,X_n}
- From: Yoshiharu Kohayakawa <yoshi@ime.usp.br>
- Date: Thu, 7 Jun 2001 15:03:56 -0300
Suponha que P é um corpo convexo no plano. Escolha n pontos X_1,...,X_n ao acaso em P independentemente, uniformemente ao acaso. Seja v o número de vértices no fecho convexo dos X_i. (1) Se P é um polígono de k vértices, entao v é basicamente normal com esperança (2/3)k\log n, e variancia (10/27)k\log n. (2) Se P é o disco, entao v é basicamente normal com esperanca an^{1/3} e variancia bn^{1/3} (a e b sao constantes conhecidas). Em ambos os casos, o resultado preciso é que a variavel v normalizada com os parametros acima converge em distribuicao para a distribuicao normal padrao N(0,1). Yoshi PS Os resultados acima sao de um Groeneboom.
-- END included message