Le problème:
N points sont donnés sur un plan à 2 dimensions. Quel est le nombre maximum de points sur la même ligne droite?
Le problème a la solution O (N 2 ): parcourez chaque point et trouvez le nombre de points qui ont le même dx / dy par rapport au point actuel. Enregistrez les relations dx / dy dans une carte de hachage pour plus d’efficacité.
Existe-t-il une meilleure solution à ce problème que O (N 2 )?
Il n'y a probablement pas de solution à ce problème qui est nettement mieux que O(n^2) dans un modèle standard de calcul.
Le problème de recherche de trois points colinéaires se réduit au problème de trouver la ligne qui passe par le plus de points, et de trouver trois points colinéaires est 3SUM-dur, ce qui signifie que de le résoudre en moins de O(n^2) serait un résultat théorique.
Voir la question précédente sur la recherche de trois points colinéaires.
Pour votre référence (à l'aide de l'connu la preuve), supposons que nous voulons répondre à un 3SUM problème tel que de trouver x, y, z dans la liste des X tels que x + y + z = 0. Si nous avions un algorithme rapide pour la colinéaires point de problème, nous avons pu utiliser cet algorithme pour résoudre le 3SUM problème comme suit.
Pour chaque x dans X, créer le point (x, x^3) (pour l'instant, nous supposons que les éléments de X sont distincts). Ensuite, vérifiez s'il existe trois points colinéaires parmi les points créés.
De voir que cela fonctionne, remarque que si x + y + z = 0 alors la pente de la droite de x à y est
(y^3 - x^3) / (y - x) = y^2 + yx + x^2
et la pente de la droite de x à z est
(z^3 - x^3) / (z - x) = z^2 + zx + x^2 = (-(x + y))^2 - (x + y)x + x^2 = x^2 + 2xy + y^2 - x^2 - xy + x^2 = y^2 + yx + x^2
A l'inverse, si la pente de x à y est égal à la pente de x à z
y^2 + yx + x^2 = z^2 + zx + x^2,
ce qui implique que
(y - z) (x + y + z) = 0,
donc soit y = z ou z = -x - y comme suffit à prouver que la réduction est valide.
Si il y a des doublons dans X, vous devez d'abord vérifier si x + 2y = 0 pour tout x et dupliquez-y de l'élément (en temps linéaire en utilisant le hachage ou O(n lg n) le temps à l'aide de tri), puis supprimer les doublons avant de réduire à la colinéaires point trouver de problème.
Si vous limitez le problème aux lignes passant par l'origine, vous pouvez convertir les points en coordonnées polaires (angle, distance par rapport à l'origine) et les trier par angle. Tous les points avec le même angle se trouvent sur la même ligne. O (n logn)
Je ne pense pas qu'il existe une solution plus rapide dans le cas général.
La transformation de Hough peut vous donner une solution approximative. Elle est approximative car la technique de binning a une résolution limitée en espace de paramètres. Par conséquent, le maximum bin vous donnera une plage limitée de lignes possibles.
Il est peu probable qu'un algorithme $ o (n ^ 2) $ existe, car le problème (vérifier même si 3 points de R ^ 2 sont colinéaires) est 3Sum-hard ( http://en.wikipedia.org/wiki / 3SUM )
Ce n'est pas une solution meilleure que O(n^2), mais vous pouvez faire ce qui suit,
2.Traduire cette nouvelle série de traductions de points à l'angle par rapport à la nouvelle (0,0).
3.Garder enregistré le nombre maximum (MSN) de points qui sont dans chaque angle.
4.Choisir le nombre maximum nombre stocké (MSN), et qui sera la solution
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
