Was ist der effizienteste Algorithmus, um eine gerade Linie zu finden, die die meisten Punkte durchläuft?

Das problem:

N Punkte gegeben sind, auf eine 2-dimensionale Ebene. Was ist die maximale Anzahl der Punkte auf der gleichen gerade Linie?

Das problem hat O(N²) Lösung: gehen Sie jeden Punkt und die Anzahl der Punkte, die die gleiche dx /dy mit Bezug auf den aktuellen Punkt. Speichern dx /dy Beziehungen in einer hash-map für Effizienz.

Gibt es eine bessere Lösung für dieses problem als O(N²)?

InformationsquelleAutor der Frage Leonid | 2010-11-14

38

Gibt es wahrscheinlich keine Lösung für dieses problem, das ist deutlich besser als O(n^2) in einer standard-Modell der Berechnung.

Das problem zu finden, drei kollinearen Punkte reduziert, um das problem zu finden, die Linie, die geht durch die Punkte und das finden der drei kollinearen Punkte ist 3SUM-hart, was bedeutet, dass die Lösung in weniger als O(n^2) Zeit, wäre ein großer theoretischer Ergebnis.

Sehen die Vorherige Frage auf der Suche nach drei kollinearen Punkte.

Für Ihre Referenz (unter Verwendung des bekannten Beweis): angenommen, wir wollen eine Antwort auf eine 3SUM problem wie die Suche nach x, y, z in die X-Liste, so dass x + y + z = 0. Hätten wir einen schnellen Algorithmus für den kollinearen Punkt-problem, könnten wir-Algorithmus zu lösen, das 3SUM problem wie folgt.

Für jedes x in X ist, erstellen Sie den Punkt (x, x^3) (für jetzt nehmen wir an, der Elemente von X Verschieden). Weiter, überprüfen Sie, ob es gibt drei kollineare Punkte aus den erstellten Punkte.

Sehen, dass dies funktioniert, beachten Sie, dass, wenn x + y + z = 0, dann ist die Steigung der geraden von x nach y ist

(y^3 - x^3) /(y - x) = y^2 + yx + x^2

und die Steigung der geraden von x nach z ist

(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

Umgekehrt, wenn die Steigung von x nach y gleich der Steigung von x nach z, dann

y^2 + yx + x^2 = z^2 + zx + x^2,

was bedeutet, dass

(y - z) (x + y + z) = 0,

also entweder y = z oder z = -x - y, wie genügt, um zu beweisen, dass die Reduktion ist gültig.

Wenn es Duplikate in X ist, überprüfen Sie zuerst, ob x + 2y = 0 für alle x und doppelte element y (in linearer Zeit mittels hashing oder O(n lg n) Zeit Sortieren), und dann entfernen Sie die Duplikate vor der Verringerung der kollinearen Punkt-finding problem.

InformationsquelleAutor der Antwort jonderry
4

Den Hough-Transformation kann Ihnen eine Ungefähre Lösung. Es ist ein Näherungswert, weil die binning-Technik hat eine begrenzte Auflösung im parameter-Raum, so dass die maximale bin Ihnen einige begrenzte Reihe von möglichen Zeilen.

InformationsquelleAutor der Antwort ergosys
4

Wenn Sie beschränken das problem auf Linien Durchgang durch den Ursprung, können Sie konvertieren Sie die Punkte in Polarkoordinaten (Winkel, Abstand vom Ursprung) und Sortieren Sie diese nach Winkel. Alle Punkte mit dem gleichen Winkel liegen auf der gleichen Linie. O(n logn)

Ich glaube nicht, dass es eine schneller Lösung im Allgemeinen Fall.

InformationsquelleAutor der Antwort Erwin J.
0

Wieder ein O(n^2) Lösung mit pseudo-code. Idee ist, erstellen Sie eine hash-Tabelle mit Zeile selbst als Schlüssel verwendet. Die Linie ist definiert durch die Steigung zwischen den beiden Punkten, Punkt, wo die Linie schneidet die x-Achse und den Punkt, wo die Linie schneidet die y-Achse.

Lösung geht davon Sprachen, wie Java, C#, wo equals-Methode und hashcode-Methoden des Objekts verwendet, für die hashing-Funktion.

Erstellen Sie ein Objekt (nennen SlopeObject) mit 3 Feldern
1. Hang //Infinity
2. Punkt, der Schnittpunkt mit der x-Achse -- poix //werden (Infinity, einige y-Wert) oder (x-Wert, 0)
3. Zählen
poix wird ein Punkt (x, y) - paar. Wenn die Linie überquert die x-Achse die poix wird (eine Zahl, 0). Wenn die Linie liegt parallel zur x-Achse dann poix = (Unendlich, auch einige), wo y-Wert ist, wo die Linie kreuzt die y-Achse.
Überschreiben der equals-Methode, wo 2 Objekte gleich sind, wenn Slope und poix gleich sind.

Hashcode überschrieben ist mit einer Funktion, die liefert hashcode basiert auf der Kombination der Werte von Slope und poix. Einige pseudo-code unten
```
Hashmap map;
foreach(point in the array a) {
    foeach(every other point b) {
        slope = calculateSlope(a, b);
        poix = calculateXInterception(a, b);
        SlopeObject so = new SlopeObject(slope, poix, 1); //Slope, poix and intial count 1.
        SlopeObject inMapSlopeObj = map.get(so);
        if(inMapSlopeObj == null) {
            inMapSlopeObj.put(so);
        } else {
            inMapSlopeObj.setCount(inMapSlopeObj.getCount() + 1);
        }
    }
}
SlopeObject maxCounted = getObjectWithMaxCount(map);
print("line is through " + maxCounted.poix + " with slope " + maxCounted.slope);
```
InformationsquelleAutor der Antwort Dheerendra Kulkarni
0

Als bereits erwähnt, gibt es wahrscheinlich keine Möglichkeit, eine Lösung für den Allgemeinen Fall, der dieses problem besser als O(n^2). Jedoch, wenn Sie annehmen, dass eine große Anzahl der Punkte liegen auf der gleichen Linie (sagen die Wahrscheinlichkeit, dass ein zufälliger Punkt in der Menge der Punkte liegen auf der Linie mit der maximalen Anzahl von Punkten p) und brauche nicht eine genaue Algorithmus ist ein randomisierter Algorithmus ist effizienter.
```
maxPoints = 0
Repeat for k iterations:
    1. Pick 2 random, distinct points uniformly at random
    2. maxPoints = max(maxPoints, number of points that lies on the 
       line defined by the 2 points chosen in step 1)
```
Beachten Sie, dass im ersten Schritt, wenn Sie wieder 2 Punkte, das liegt auf der Linie mit der maximalen Anzahl der Punkte, die, erhalten Sie die optimale Lösung. Angenommen n ist sehr groß (d.h. wir können Sie behandeln, die Wahrscheinlichkeit, 2 wünschenswert Punkte da die Probenahme mit Ersatz), die Wahrscheinlichkeit dieses Ereignisses ist p^2 ein. Daher ist die Wahrscheinlichkeit, eine suboptimale Lösung nach k Iterationen ist (1 - p^2)^k.

Angenommen, Sie tolerieren können ein falsch-negativ-rate = err. Dann wird dieser Algorithmus läuft in O(nk) = O(n * log(err) /log(1 - p^2)). Wenn beide n und p sind groß genug, das ist deutlich effizienter als O(n^2). (d.h. es Sollte n = 1.000.000 und du weißt, es gibt mindestens 10.000 Punkte liegen auf der gleichen Linie. Dann ist n^2 wäre erforderlich, auf der Größenordnung von 10^12 Operationen, während der randomisierten Algorithmus erfordern würde, auf die Größenordnung von 10^9 Operationen bekommen Sie eine Fehler-rate von weniger als 5*10^-5.)

InformationsquelleAutor der Antwort Tony Cai
-1

Es ist unwahrscheinlich, dass für eine $o(n^2)$ - Algorithmus zu existieren, da das problem (noch überprüfen, ob 3 Punkte im R^2 sind kollinear) ist 3Sum-hart (http://en.wikipedia.org/wiki/3SUM)

InformationsquelleAutor der Antwort user695652
-3

Dies ist nicht eine Lösung besser als O(n^2), aber Sie können Folgendes tun,
1. Für jeden Punkt konvertieren konvertieren Sie zuerst, als ob es, wo in der (0,0) - Koordinate, und dann tun die äquivalente übersetzung für all die anderen Punkte, indem Sie diese auf die gleiche x -, y-Abstand, den Sie benötigt, um zu bewegen, die original eingegebenen Punkt.
2.Übersetzen Sie diese neue Reihe von übersetzten Punkte, um den Winkel mit Bezug auf die neuen (0,0).

3.Halten Sie gespeichert die maximale Anzahl (MSN) der Punkte, die in jedem Winkel.

4.Wählen Sie die maximal gespeicherte Nummer (MSN), und das wird die Lösung sein

InformationsquelleAutor der Antwort

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.