Encontrar el mayor conjunto de puntos de diámetro limitado

Dados los puntos en y una distancia encuentre el subconjunto más grande de estos puntos de tal manera que la distancia euclidiana de ninguno de ellos exceda . $p_1,\ldots,p_n$ $\mathbb{R}^{d}$ $l$ $l$

¿Cuál es la complejidad de este problema?

En el gráfico sobre los puntos que tiene un borde cuando la distancia de dos puntos es como máximo , el problema es equivalente a encontrar una camarilla máxima. Lo contrario puede no ser válido, porque no todos los gráficos se pueden obtener de esta manera (un ejemplo es la estrella para ). Por lo tanto, una pregunta relacionada es: ¿qué se sabe sobre esta clase de gráficos? $l$ $K_{1,7}$ $d=2$

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

Observe que si

es fija, hay un algoritmo de tiempo P "trivial": desde un conjunto tal está encerrado en una bola de radio de

, y sin pérdida de generalidad el balón es mínimo (es decir, toques

puntos), simplemente enumere sobre todos los subconjuntos. Puede hacerlo mejor, pero desde el punto de vista de la complejidad, el problema es "fácil".

d

$d$

l / 2

$l/2$

d + 1

$d+1$

Suresh Venkat

No creo que sea cierto que el conjunto óptimo esté necesariamente encerrado en una bola de radio l / 2. En el plano, por ejemplo, los tres vértices de un triángulo equilátero de longitud lateral l no están tan encerrados.

David Eppstein

ah cierto. pero la enumeración debería funcionar independientemente.

Suresh Venkat

Puedes enumerar los subconjuntos dentro de las bolas, pero si haces el radio 1/2, entonces no encontrarás algunos subconjuntos de bajo diámetro, y si haces el radio más alto que eso, no es obvio cómo recortar los subconjuntos para que Tiene bajo diámetro.

David Eppstein

¿por qué no puedo enumerar los subconjuntos, encontrar una bola de cierre mínima y calcular la cardinalidad dentro de cada uno?

Suresh Venkat

Respuestas:

Hay un algoritmo de tiempo para la versión bidimensional de este problema en mi artículo con Jeff Erickson, " Iterado vecinos más cercanos y encontrando politopos mínimos ", Disco. Comp. Geom 11: 321-350, 1994. En realidad, el documento analiza principalmente el doble problema: dado el número de puntos en el subconjunto, encuentre el diámetro más pequeño posible; pero usa el problema que usted describe como una subrutina. Al menos en el momento en que lo escribimos, no sabíamos nada subexponencial para dimensiones superiores (aunque si el subconjunto tiene solo puntos, la parte exponencial puede hacerse dependiente de lugar de $O(n^3\log n)$ $k$ $k$ $n$ utilizando técnicas en el mismo artículo).

David Eppstein
fuente

La aproximación es bastante fácil si está interesado en el subconjunto más pequeño con diámetro como máximo . Un algoritmo de tiempo lineal usando cuadrículas es ahora "estándar". La constante probablemente sería algo así como . $(1+\epsilon)l$ $2^{O(1/\epsilon^d)}$

Se está trabajando para encontrar la bola más pequeña que contenga k puntos, pero el problema del diámetro es inherentemente más difícil. Para ver por qué, un buen punto de partida es el papel de Clarkson-Shor para calcular el diámetro en 3d.

Por cierto, para las dimensiones altas, el problema de la bola es aproximable en tiempo exponencial en (o algún ruido similar), mediante el uso de núcleos (¡pero no en la dimensión!). Dudo que este enfoque pueda extenderse a este problema, pero podría estar equivocado. $O(1/\epsilon^2)$

Sariel Har-Peled
fuente