Finden Sie alle kollinearen Punkte in einem gegebenen Satz

Dies ist ein interview-Frage: "Finden Sie alle kollinearen Punkte in einem gegebenen Satz".

So wie ich das verstehe, Fragen Sie zum drucken der Punkte, die liegen in der selben Zeile (und jeder zwei Punkte sind immer kollinear). Ich würde Folgendes vorschlagen.

  1. Wir stellen zwei Arten Line (paar Doppel) und die Point (paar von ganzen zahlen).
  2. Erstellen Sie eine multimap : HashMap<Line, List<Point>)
  3. Schleife über alle Paare der Punkte und für jedes paar: berechnen Sie die Line verbinden Sie die Punkte und fügen Sie die Zeile mit diese Punkte die multimap.

Schließlich die multimap enthält die Zeilen, die Schlüssel und eine Liste kollinearen Punkte für jede Zeile als Wert.

Die Komplexität ist O(N^2). Macht es Sinn ? Gibt es bessere Lösungen ?

Ich bin immer ein Gefühl, dass dies nicht die vollständige Beschreibung des Problems. Ein Teil war verloren.
Warum denken Sie so ?
Genau wie du gesagt hast, n^2 die Lösung ist trivial und es gibt keine bessere: Ergebnis der Größe ist proportional zu n^2.
BTW, man kann nicht für jede Linie mit einem paar von ganzen zahlen, müssen Sie ein paar von reellen zahlen.
Ja, aber das ist das problem, nicht dass die denken oder Algorithmus. Es ist Fragen, wie die Summe der Quadrate der Werte in der NxN-matrix. Wie lösen Sie es? Gehen Sie durch alle Werte, und fügen Sie jedes Quadrat um das Ergebnis.

InformationsquelleAutor Michael | 2010-12-29

  1. 8

    Kollinearen hier nicht wirklich sinnvoll, es sei denn, Sie fix auf 2 Punkte, um mit zu beginnen. So zu sagen, "finden Sie alle kollinearen Punkte in einem gegebenen Satz" macht nicht viel Sinn meiner Meinung nach, es sei denn, Sie fix auf 2 Punkte und testen Sie die andere, um zu sehen, ob Sie kollinear.

    Vielleicht eine bessere Frage ist, was ist die maximale Anzahl von kollinearen Punkten in dem angegebenen Satz? In diesem Fall könnten Sie fix auf 2 Punkte (einfach 2 Schleifen), dann Schleife über die anderen Punkte und prüfen Sie, dass die Steigung übereinstimmt, zwischen dem festen Punkte und die anderen Punkte. Sie könnte so etwas wie dies für Sie, dass der check, vorausgesetzt, die Koordinaten sind integer (Sie könnte sich ändern, parameter-Typen zu verdoppeln sonst).

    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Returns whether 3 points are collinear
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

    So die Logik wird:

    int best = 2;
for (int i = 0; i < number of points; ++i) {
  for (int j = i+1, j < number of points; j++) {
    int count = 2;
    for (int k = 0; i < number of points; ++k) {
      if (k==i || k==j)
        continue;

      check that points i, j and k are collinear (use function above), if so, increment count.
    }
    best = max(best,count); 
  }
}
    Nun, für dieses problem könnte man besser machen, in O(n^2*logn), aber ich bin mir nicht sicher, ob ich post sollte eine Antwort auf die veränderte Frage 🙂 aber +1 sowieso.
    Es war einfach das erste, woran ich dachte. Die andere Idee die ich hatte, war mit einer Bitmaske und-Prüfung alle möglichen Sätze der Punkte aus den original-sets, aber ich war mir nicht sicher, wie groß seine ursprünglichen Satz von Punkten war. Aber hey, du bist der TC rot algo Kerl, so dein Wort hat mehr Gewicht als meine, würd ich sagen, posten Sie Ihre Antwort, wenn Sie bessere Ideen :).
    Fragen wir einen Autor, wenn er genehmigt das Thema zu wechseln 🙂 Oder ich könnte Sie E-Mail, die Idee ist echt einfach.
    Würde dies nicht die algo laufen in O(n^3)?
    Warum ist die Berechnung der Steigung zwischen i und j wichtig ist, wenn es nie userd später auf?

    InformationsquelleAutor dcp

  2. 5

    lösen das problem in zwei Ebenen, konvertieren Sie alle Punkte an Liniensegmenten. Und führen Sie dann eine plane sweep zu berichten, alle Kreuzungen. Die Linien in der dualen Ebene wird übergeben, durch denselben Punkt darstellt kollineare Punkte. Und das plane-sweep können sein getan in O(nlogn) Zeit.

    Man könnte hinzufügen wollen, dass die Konstruktion der dual-line-Anordnung in O(n^2).
    Bau der zwei Leitungen in O(n), da gibt es eine Zeile pro Punkt, und die Parameter der Linie sind Funktionen der Parameter der Punkt. Jedoch, wie viele Schnittpunkte gibt es zwischen der n-Linien im schlimmsten Fall? Betrachten wir ein Gitter, (n/2)*(n/2), so ist es BigTheta(n^2), also die Ebene fegen, kann nicht sein getan in O(n lg n) Zeit.
    Sergeev Bau der Linie Anordnung! dauert Zeit O(n^2), da wie gesagt die kombinatorische Komplexität ist bereits in \Omega(n^2). Auch da das ursprüngliche problem 3SUM-hart, seine unwahrscheinlich, dass ein sub-quadratischen Algorithmus existiert.
    Ja, das Wort "Anordnung", das war der Punkt der Verwirrung.

    InformationsquelleAutor sandeep

  3. 2

    Werfen Sie einen Blick auf die beiden beschriebenen Methoden in http://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/lines.html .

    Finden 4 oder mehr kollineare Punkte gegeben N Punkte, die brute-force-Methode über eine Zeit-Komplexität von O(N^4), aber eine bessere Methode gibt es in O(N^2 log N).

    Vielen Dank für das teilen! Das ist besser als die obige Antwort (N^3).

    InformationsquelleAutor wsw

  4. 0

    Ich denke, die Absicht ist zu finden, eine Linie, die durchläuft maximale Anzahl der Punkte zu identifizieren oder mit diesem set von kollinearen Punkte. Diese link gibt ein N^2(logN) Lösung für dieses problem

    Ich glaube, die Lösung oben löst dieses problem auch in O(N^2) 🙂
    dieser link ist gebrochen

    InformationsquelleAutor Neera

  5. 0

    Sind Sie sicher, dass Ihre Analyse der Laufzeit ist die richtige? Sie sagen, um eine Schleife über alle Paare von Punkten, von denen gibt es n*(n-1)/2, also O(n^2). Anschließend fügen Sie die Zeile und die paar Punkte auf der Karte. Aber ich glaube nicht, dass die Zeit, um eine solche Linie + Punkt Verbindung ist konstant. Dies bedeutet, dass insgesamt Ihre Zeit ist O(n^2 log n) nicht konstant, mal n^2, was O(n^2) bedeutet.

    Also die eigentliche Frage wäre, angesichts der Tatsache, dass es getan werden kann in der Zeit O(n^2 log n) kann es getan werden in einer Zeit von O(n^2). Klar O(n^2) gibt eine untere Schranke, wie Sie müssen zumindest drucken Sie jedes paar von Punkten, von denen es O(n^2). Mein Gefühl ist, das ist eine ganz Allgemeine Sortier-problem und dass man nicht erwarten kann, besser als O(n^2 log n) im Allgemeinen. Aber einen vollständigen Beweis, dass die Tat kann nicht-trivial.

    Andere Sache, die davor hüten, ist, dass das set enthalten kann null oder ein Punkte, und so werden Sie brauchen, um zu überprüfen, dass Ihr Algorithmus handhabt diesen Fällen richtig, anders schreiben Sonderfälle für diese.

    Die untere Schranke von $O(n^2)$ scheint dicht nach Kapitel 2 dieses Ph. D. thesis. Eine $O(n^2)$ - Algorithmus wird in diesem paper: H. Edelsbrunner, J. O ' Rourke, and R. Seidel. Bau arrangements von Linien und hyperplanes mit Anwendungen. SIAM J. Comput., 15:341.

    InformationsquelleAutor Bill

Schreibe einen Kommentar