Aproximando medidas de extensão de pontos

Apresentamos uma técnica geral para aproximar vários descritores da extensão de um conjunto P de n pontos em R d quando a dimensão d é uma constante fixa arbitrária. Para uma medida de extensão μ e um parâmetro ε > 0, ela computa em tempo O ( n + 1/ε O (1) ) um subconjunto Q ⊆ P de tamanho 1/ε O (1) , com a propriedade de que (1 − ε)μ( P ) ≤ μ( Q ) ≤ μ( P ). As aplicações específicas de nossa técnica incluem algoritmos de ε-aproximação para (i) calcular diâmetro, largura e a menor caixa envolvente, bola e cilindro de P , (ii) manter todas as medidas anteriores para um conjunto de pontos em movimento, e (iii) ajustar esferas e cilindros através de um conjunto de pontos P . Nossos algoritmos são consideravelmente mais simples e mais rápidos em muitos casos do que algoritmos conhecidos anteriormente.