Trouver le plus grand ensemble de points de diamètre limité

Étant donné les points dans et une distance trouver le plus grand sous-ensemble de ces points de sorte que la distance euclidienne de deux d'entre eux ne dépasse pas . $p_1,\ldots,p_n$ $\mathbb{R}^{d}$ $l$ $l$

Quelle est la complexité de ce problème?

Dans le graphique sur les points qui ont une arête chaque fois que la distance de deux points est au plus , le problème revient à trouver une clique maximale. L'inverse peut ne pas tenir, car tous les graphiques ne peuvent pas être obtenus de cette façon (un exemple est l'étoile pour ). Par conséquent, une question connexe est: que sait-on de cette classe de graphiques? $l$ $K_{1,7}$ $d=2$

ds.algorithms reference-request cg.comp-geom Marcus Ritt
la source

Notez que si

est fixe, il existe un algorithme de temps P "trivial": puisqu'un tel ensemble est enfermé dans une boule de rayon

, et sans perte de généralité la balle est minimale (ie touche

points), juste énumérer tous les sous-ensembles. Vous pouvez faire mieux, mais du point de vue de la complexité, le problème est "facile".

d

$d$

l / 2

$l/2$

d + 1

$d+1$

Suresh Venkat

Je ne pense pas qu'il soit vrai que l'ensemble optimal soit nécessairement enfermé dans une boule de rayon l / 2. Dans le plan, par exemple, les trois sommets d'un triangle équilatéral de longueur latérale l ne sont pas ainsi enfermés.

David Eppstein

ah vrai. mais l'énumération devrait fonctionner malgré tout.

Suresh Venkat

Vous pouvez énumérer les sous-ensembles à l'intérieur des boules, mais si vous créez le rayon l / 2, vous ne trouverez pas de sous-ensembles de faible diamètre, et si vous augmentez le rayon, il n'est pas évident de réduire les sous-ensembles afin qu'ils ont un faible diamètre.

David Eppstein

pourquoi ne puis-je pas énumérer les sous-ensembles, trouver une boule englobante min et calculer la cardinalité à l'intérieur pour chacun?

Suresh Venkat

Réponses:

Il y a un algorithme de temps pour la version bidimensionnelle de ce problème dans mon article avec Jeff Erickson, " Itération des voisins les plus proches et recherche de polytopes minimaux ", Disc. Comp. Geom. 11: 321-350, 1994. En fait, l'article examine principalement le double problème: étant donné le nombre de points dans le sous-ensemble, trouver le plus petit diamètre possible; mais il utilise le problème que vous décrivez comme un sous-programme. Au moins au moment où nous l'avons écrit, nous ne savions rien de sous-exponentiel pour les dimensions supérieures (bien que si le sous-ensemble ne contient que points, la partie exponentielle peut être rendue dépendante de plutôt que de $O(n^3\log n)$ $k$ $k$ $n$ en utilisant des techniques dans le même article).

David Eppstein
la source

L'approximation est assez facile si vous êtes intéressé par le plus petit sous-ensemble avec un diamètre au plus . Un algorithme de temps linéaire utilisant des grilles est désormais "standard". La constante serait probablement quelque chose comme . $(1+\epsilon)l$ $2^{O(1/\epsilon^d)}$

Il y a du travail pour trouver la plus petite boule contenant k points, mais le problème du diamètre est intrinsèquement plus difficile. Pour voir pourquoi, un bon point de départ est le papier Clarkson-Shor pour calculer le diamètre en 3D.

$O(1/\epsilon^2)$

Sariel Har-Peled
la source