Wenn 3 Punkte kollinear sind

Wenn eine Menge von Punkten den effizientesten Algorithmus zum Bestimmen, ob 3 Punkte der Menge kollinear sind.$S$$p_1,..,p_2$

Das Problem ist, dass ich mit der allgemeinen Definition begonnen habe, aber ich kann das Problem nicht weiter lösen.

Was können wir über kollineare Punkte im Allgemeinen sagen? 3 Punkte $a,b,c$ sind kollinear, wenn der Abstand $d(a,c) = d(a,b)+d(b,c)$ ist, wenn $b$ zwischen $a$ und $c$ .

Der naive Ansatz hat eine zeitliche Komplexität von $O(n(n-1)(n-2))=O(n^3)$ .

Wie soll dieses Problem gelöst werden? Was sollte der nächste Schritt sein?

Eine einfache Möglichkeit besteht darin, einen Punkt x zu fixieren $x$, die Steigung der Linie xy zu berechnen $xy$und sie für jeden zweiten Punkt y in einer Hash-Tabelle zu speichern $y$. Wenn es eine Kollision gibt, haben wir kollineare Punkte mit $x$ . Dies nimmt $O(n)$ (wenn wir annehmen, dass Hash-Tabellenoperationen $O(1)$ ). Wir machen das dann für jeden Punkt $x$ zum Zeitpunkt $O(n^2)$ .

Auch wenn Sie sich der Punkt-Linien-Dualität bewusst sind (siehe Artiums Kommentar unten), reduziert sich dies auf die Überprüfung der möglichen Schnittpunkte von Linien, verwendet aber auch Hash-Tabellen.$n^2$$n$

Es ist auch offen, ob dies in subquadratischer Zeit möglich ist, da dieses Problem 3-SUM schwer ist. Bitte beziehen Sie sich auf diese Antwort .