[obm-l] Contagem de grupinhos de pontos - Análise Numérica

["Bruno França dos Reis" <bfreis@xxxxxxxxx>]

Olá.

Sejam I um intervalo da reta e I_1, ..., I_n, n intervalos disjuntos, todos contidos em I.
Sejam (a_k)_1, ..., (a_k)_(p_k), p_k pontos do intervalo I_k, para k = 1, ..., n.

Meu problema é: dado o conjunto desses números {a_i_j}, quero determinar n. Algumas informações que podemos assumir para simplificar o problema, válidas na maior parte dos casos:
(a) os pontos dentro de um mesmo intervalo I_k estão "bem distribuidos"
(b) os tamanhos dos intervalos I_k são pequenos se comparados às distâncias entre os intervalos.
(c) I está contido em [0, 1]

Para ilustrar, o que eu tenho é mais ou menos isso:
-----------(I_1)-----------(I_2)-----------(I_3)------------

Já tive algumas idéias para resolver o problema, mas elas não me servem pois:
(i) soma{k = 1..n} (p_k) é grande
(ii) e na verdade eu tenho que fazer essa mesma análise para MUITOS conjuntos de pontos {a_i_j} independentes

Para dar as ordens de grandeza com as quais gostaria de trabalhar, tenho uns 2000 conjuntos a determinar seus "n", cada um dos quais com algo como 1000 pontos.

Em outras palavras: preciso de um algoritmo RÁPIDO. Alguém tem alguma idéia? Alguém já viu isso e poderia me indicar qualquer referência?

Alguns problemas que podemos encontrar: AS VEZES, há alguns intervalos I_k MUITO próximos (isto é: existe k tal que a distância entre I_k e I_(k+1) é pequena se comparada ao tamanho de cada um desses intervalos), mas as distâncias entre seus pontos internos é muito menor que a distância entre os intervalos.

Qualquer comentário será bem vindo, estou precisando de idéias mesmo que não sejam otimizadas.


Obrigado,
Bruno


-- 
Bruno FRANÇA DOS REIS

msn: brunoreis666@xxxxxxxxxxx
skype: brunoreis666
tel: +33 (0)6 28 43 42 16

e^(pi*i)+1=0