Étant donné un ensemble de points, trouvez si l'un des trois points est colinéaire

Quel est le meilleur algorithme pour trouver si les trois points sont colinéaires dans un ensemble de points-dire n. Veuillez également expliquer la complexité, si elle n'est pas négligeable.

Grâce
Bala

source d'informationauteur Boolean

  1. 15

    Si vous pouvez trouver une meilleure que O(N^2) l'algorithme, vous pouvez le publier!

    Ce problème est 3-SOMME Duret si il y a un sous-quadratique de l'algorithme (c'est à dire mieux que O(N^2)) car c'est un problème ouvert. De nombreuses communes de calcul des problèmes de géométrie (y compris la vôtre) ont été montré pour être 3SUM dur et cette classe de problèmes est en croissance. Comme NP-Dureté, la notion de 3SUM de la Dureté de l'a prouvé utile pour prouver la "ténacité" de certains problèmes.

    Une preuve que votre problème est 3SUM dur, reportez-vous à l'excellent surver papier ici: http://www.cs.mcgill.ca/~jking/documents/3sumhard.pdf

    Votre problème apparaît à la page 3 (idéalement appelé 3-POINTS SUR la LIGNE) dans le mentionné ci-dessus le papier.

    Donc, le mieux connu de l'algorithme est O(N^2) et que vous l'avez déjà 🙂

  2. 6

    Une simple O(d*N^2) le temps et l'espace de l'algorithme, où d est la dimension et N est le nombre de points (probablement pas optimale):

    • Créer un cadre de sélection autour de l'ensemble des points (il est assez grand donc il n'y a pas de points sur la frontière)
    • Pour chaque paire de points, calcul de la ligne passant à travers eux.
    • Pour chaque ligne, calculer ses deux points de collision avec la boîte englobante.
    • Les deux points de collision définir la ligne d'origine, donc si il y a aucune correspondance des lignes qu'ils vont produire le même deux points de collision.
    • D'utiliser un hachage ensemble pour déterminer s'il existe un double point de collision paires.
    • Il y a 3 points colinéaires si et seulement si il y avait des doublons.
  3. 4

    Un autre simple (peut-être même trivial) solution qui permet de ne pas utiliser une table de hachage, s'exécute en O(n2log n) le temps, et utilise O(n) de l'espace:

    Laisser S être un ensemble de points, nous allons décrire un algorithme qui détermine si ou non S contient des trois points colinéaires.

    1. Pour chaque point o dans S faire:
      1. Passer une ligne L parallèle à la x-axe o.
      2. Remplacer chaque point dans S ci-dessous Lavec son reflet. (Par exemple si L est le x axe, (a,-x) pour x>0 deviendra (a,x) après la réflexion). Laissez le nouvel ensemble de points S'
      3. L'angle de chaque point p dans S'est le droit de l'angle du segment po avec la ligne L. Permettez-nous de trier les points de S' par leurs angles.
      4. Promenade à travers le tri des points dans S'. Si il y a deux points consécutifs qui sont colinéaires o - return true.
    2. Si non colinéaires points ont été trouvés dans la boucle de retour faux.

    La boucle s'exécute n fois, et à chaque itération effectue nlog n étapes. Il n'est pas difficile de prouver que si il y a trois points sur une ligne, qu'ils soient trouvés, et nous trouverons rien sinon.