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

16

Étant donné les points dans R d et une distance l, trouver le plus grand sous-ensemble de ces points de sorte que la distance euclidienne de deux d'entre eux ne dépasse pas l .p1,,pnRdll

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 K 1 , 7 pour ). Par conséquent, une question connexe est: que sait-on de cette classe de graphiques?lK1,7d=2

Marcus Ritt
la source
3
Notez que si est fixe, il existe un algorithme de temps P "trivial": puisqu'un tel ensemble est enfermé dans une boule de rayon l / 2 , et sans perte de généralité la balle est minimale (ie touche d + 1 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". dl/2d+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
1
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:

16

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 k points, la partie exponentielle peut être rendue dépendante de k plutôt que de nO(n3logn)kkn en utilisant des techniques dans le même article).

David Eppstein
la source
9

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 2 O ( 1 / ϵ d ) .(1+ϵ)l2O(1/ϵ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/ϵ2)

Sariel Har-Peled
la source