Encontrar o maior conjunto de pontos de diâmetro limitado

Dados os pontos em e uma distância encontro o maior subconjunto desses pontos, de modo que a distância euclidiana de nenhum deles exceda . $p_1,\ldots,p_n$ $\mathbb{R}^{d}$ $l$ $l$

Qual é a complexidade desse problema?

No gráfico sobre os pontos que têm uma aresta sempre que a distância de dois pontos é no máximo , o problema é equivalente a encontrar uma camarilha máxima. O inverso pode não se sustentar, porque nem todo gráfico pode ser obtido dessa maneira (um exemplo é a estrela para ). Portanto, uma pergunta relacionada é: o que se sabe sobre essa classe de gráficos? $l$ $K_{1,7}$ $d=2$

ds.algorithms reference-request cg.comp-geom Marcus Ritt
fonte

Observe que se

é fixo, existe um algoritmo "trivial" no tempo P: como esse conjunto é encerrado em uma bola de raio

, e sem perda de generalidade, a bola é mínima (ou seja, toca em

pontos), apenas enumere sobre todos os subconjuntos. Você pode fazer melhor, mas do ponto de vista da complexidade, o problema é "fácil".

d

$d$

l / 2

$l/2$

d + 1

$d+1$

Suresh Venkat

Não acho que seja verdade que o conjunto ideal esteja necessariamente envolvido em uma bola de raio l / 2. No plano, por exemplo, os três vértices de um triângulo equilátero de comprimento lateral l não são tão fechados.

David Eppstein

ah verdade. mas a enumeração deve funcionar independentemente.

Suresh Venkat

Você pode enumerar subconjuntos dentro de bolas, mas se você fizer o raio l / 2, não encontrará subconjuntos de baixo diâmetro e, se o raio for maior do que isso, não será óbvio como aparar os subconjuntos para que eles tem baixo diâmetro.

David Eppstein

por que não consigo enumerar subconjuntos, encontrar uma bola minúscula e calcular a cardinalidade interna de cada uma?

Suresh Venkat

Respostas:

Existe um algoritmo de tempo para a versão bidimensional desse problema em meu artigo com Jeff Erickson, " Iterado vizinhos mais próximos e encontrando polítopos mínimos ", Disc. Comp. Geom. 11: 321-350, 1994. Na verdade, o artigo analisa principalmente o problema duplo: dado o número de pontos no subconjunto, encontre o menor diâmetro possível; mas usa o problema que você descreve como uma sub-rotina. Pelo menos no momento em que o escrevemos, não sabíamos nada subexponencial para dimensões mais altas (embora, se o subconjunto tenha apenas pontos, a parte exponencial possa ficar dependente de em vez de $O(n^3\log n)$ $k$ $k$ $n$ usando técnicas no mesmo artigo).

David Eppstein
fonte

A aproximação é bem fácil se você estiver interessado no menor subconjunto com diâmetro no máximo . Um algoritmo de tempo linear usando grades agora é "padrão". A constante provavelmente seria algo como . $(1+\epsilon)l$ $2^{O(1/\epsilon^d)}$

Há algum trabalho para encontrar a menor bola contendo k pontos, mas o problema do diâmetro é inerentemente mais difícil. Para entender por que, um bom ponto de partida é o artigo de Clarkson-Shor para calcular o diâmetro em 3d.

BTW, para dimensões altas, o problema da bola é exponencial no tempo aproximado em (ou algum ruído semelhante), usando conjuntos de cores (mas não na dimensão!). Eu duvido que essa abordagem possa ser estendida a esse problema, mas posso estar errado. $O(1/\epsilon^2)$

Sariel Har-Peled
fonte