Trouver le point central dans un ensemble de points métriques dans l'espace, en moins de ?

J'ai un ensemble de points qui sont définis dans un espace métrique - donc je peux mesurer une «distance» entre les points mais rien d'autre. Je veux trouver le point le plus central de cet ensemble, que je définis comme le point avec la somme minimale des distances à tous les autres points. Le calcul métrique est lent et doit donc être évité autant que possible. $n$

La manière évidente de trouver ce point utilise calculs de distance métrique, car il (a) calcule simplement pour chaque point la somme des distances à tous les autres points, puis (b) prend le point minimum. $n^2$

Existe-t-il un moyen de le faire dans des comparaisons de distance inférieures à ? (Utiliser probablement l'inégalité du triangle d'une manière ou d'une autre, ce qui devrait être le cas avec ma métrique.) $O(n^2)$

Une bonne approximation peut suffire s'il n'existe pas de méthode exacte.

complexity-theory computational-geometry lower-bounds search-problem Logistique portes ouvertes
la source

Sans l'inégalité du triangle (ou une autre façon d'obtenir des informations sur les arêtes non mesurées), est la seule solution; cela peut être vu par un argument antagoniste.

O (n^{2})

$O(n^2)$

Kittsil

Supposons que l'inégalité du triangle soit disponible - elle devrait l'être pour ma métrique.

Open Door Logistics

Il s'agit essentiellement de calculer les radios d'un graphe avec égalité triangulaire.

Kaveh

@Kaveh Je suppose que vous voulez dire le rayon ... sauf si le graphique a un bord cassé. Je m'assure car il y a trop de vocabulaire que je ne connais pas. --- Mais c'est alors un graphe complet, et la taille d'entrée n'est que le nombre de sommets.

babou

@OpenDoorLogistics S'il n'a pas l'inégalité du triangle, ce n'est pas un espace métrique, par définition. Veuillez clarifier la question: si vous savez que c'est un espace métrique, alors vous savez qu'il a l'inégalité du triangle; si vous ne savez pas qu'il a l'inégalité du triangle, vous ne pouvez pas prétendre qu'il s'agit d'un espace métrique.

David Richerby

Réponses:

Non. Vous ne pouvez pas faire mieux que dans le pire des cas. $\Theta(n^2)$

Considérons un arrangement de points où chaque paire de points est à une distance de . (Il s'agit d'une configuration possible.) Ensuite, vous ne pouvez pas faire mieux que d'examiner chaque bord. En particulier, s'il y a un bord que vous n'avez pas examiné, un adversaire pourrait choisir la longueur de ce bord soit , ou $1$ $0.9$ $1.0$ $1.1$ ; tous ces choix sont cohérents avec toutes les autres observations que vous avez faites et avec les exigences d'une métrique (par exemple, avec l'inégalité du triangle), donc les trois sont possibles; mais ils nécessitent des sorties différentes. Ainsi, si votre algorithme n'examine pas ce bord et produit ensuite quelque chose, un adversaire peut toujours choisir une longueur pour le bord non examiné qui rendra la sortie de votre algorithme erronée.

Cependant, si vous savez que tous les points vivent dans (même si on ne vous donne pas leurs coordonnées), alors le problème peut être résolu en mesurant les distances , en supposant aucune dégénérescence (aucun sous-ensemble de points sont coplanaires). $\mathbb{R}^d$ $O((d+1)n)$ $d+1$

En particulier, choisissez au hasard points. Ce seront des points d'ancrage. Compte tenu de leurs distances par paires, vous pouvez calculer pour elles des coordonnées cohérentes avec leurs distances par paires. Maintenant, pour chaque autre point , calculez la distance de à chacun des points d'ancrage. En utilisant la triangulation et ces distances, vous pouvez calculer l'emplacement de par rapport aux points d'ancrage et donc les coordonnées pour . Faites ceci pour chaque point non d'ancrage $d+1$ $P$ $P$ $P$ $P$ $P$ . Vous avez maintenant des coordonnées pour chaque point, et vous pouvez utiliser ces coordonnées pour trouver le point central sans demander à l'oracle de vous donner des distances plus par paires. Je ne sais pas si cette dernière étape peut se faire plus rapidement que le temps , mais il peut être fait sans mesurer des distances plus de paires. $O(n^2)$

DW
la source

Vous avez

points dans la dimension

. Même regarder toutes les coordonnées de l'entrée nécessite un temps

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

Louis

@Louis La question ne dit rien sur les dimensions et n'est pas sûre qu'il s'agisse d'une métrique. Tout ce que nous avons, c'est l'inégalité triangulaire. La vue correcte est donc celle du commentaire de Kaveh: sous forme de graphique complet. Cela correspond à cette réponse. Mais je n'ai aucune idée si elle est cohérente avec une métrique fixe lorsque

croît sans limite.

n

$n$

babou

@DW Merci - pourrions-nous faire mieux dans le cas moyen? Ceci est motivé par un problème du monde réel, donc les données sont susceptibles d'être «moyennes» (quoi que cela puisse signifier).

Open Door Logistics

@all - excuses pour la confusion re: metric (je suis un profane en CS théorique). Ma fonction de distance obéit définitivement aux 4 critères pour un espace métrique, selon la définition Wikipedia d'un lien d' espace métrique .

Open Door Logistics

@OpenDoorLogistics, j'ai ajouté un cas spécial où il semble possible de faire mieux.

Découvrez les travaux de Piotr Indyk sur les algorithmes rapides pour les espaces métriques. ( Algorithmes sublinéaires pour les problèmes d'espace métrique , dans les actes du STOC '99 , pp.428–434. ACM, 1999; PS ) La section 3 donne un algorithme approximatif à 1 médiane en temps linéaire.

user71641
la source

Pourriez-vous donner un résumé de l'algorithme? Nous recherchons idéalement des réponses complètes, plutôt que des liens vers du contenu externe.

David Richerby

Toutes mes excuses pour la réponse très lente. Je ne vérifie évidemment pas StackExchange très souvent. Je pense que cela me prendrait plus d'une heure pour écrire un résumé à mi-chemin décent, alors que le papier de Piotr est magnifiquement écrit, explique l'algorithme très clairement et a toutes les définitions précises à côté. Je recommanderais donc personnellement d'utiliser ce contenu externe de haute qualité plutôt que le contenu interne de qualité moyenne que je pourrais produire. La réponse courte est la suivante: si vous souhaitez simplement trouver une médiane approximative, vous pouvez le faire en temps linéaire O (n).

user71641