Teilen einer Punkteebene in zwei gleiche Hälften

Erhält eine 2-dimensionale Ebene, in der es sind n Punkte. Ich brauche generieren, die Gleichung der Linie, die trennt die Ebene so, dass es n/2-Punkte auf der einen Seite und der n/2 Punkte auf der anderen. (übrigens ist diese nicht zu Hause arbeite, bin ich nur versuchen, das problem zu lösen)

InformationsquelleAutor der Frage mousey | 2010-06-23

26

Ich angenommen haben, dass die Punkte unterscheidbar sind, sonst könnte es nicht sogar sein, dass eine solche Linie.

Wenn die Punkte unterschiedliche sind, dann ist eine solche Zeile existiert immer und ist möglich, zu finden über eine deterministische O(nlogn) Zeit Algorithmus.

Sagen die Punkte sind P1, P2, ..., P2n. Nehme an, Sie sind nicht alle auf der gleichen Linie. Wenn Sie waren, dann, können wir leicht die form der splitting-Zeile.

Zuerst übersetzen Sie die Punkte so, dass alle Koordinaten (x und y) positiv sind.

Nun nehmen wir magisch hatte einen Punkt Q auf der y-Achse so, dass keine Linie gebildet durch die Punkte (d.h. eine unendliche Linie Pi-Pj) geht durch Q.

Nun, da Q nicht liegen innerhalb der konvexen Hülle der Punkte, können wir leicht sehen, dass wir können, um die Punkte durch eine sich drehende Linie, die durch Q. Für einen bestimmten Winkel der Drehung, die Hälfte der Punkte liegen auf der einen Seite und die andere Hälfte liegen wird, auf der anderen dieser rotierenden Linie, oder, in anderen Worten, wenn wir die Punkte, die sortiert wird, indem die Steigung der geraden Pi-Q, wir konnten wählen Sie eine Kurve zwischen den (median) - te und (median+1)th Punkte. Diese Auswahl kann durchgeführt werden in O(n) Zeit durch jede lineare Zeit-Auswahl-Algorithmus ohne die Notwendigkeit für die Sortierung der Punkte.

Nun wählen Sie den Punkt Q.

Sagen, Q (0,b).

Angenommen, Q kollinear mit P1 (x1,y1) und P2 (x2,y2).

Dann haben wir, dass

(y1-b)/x1 = (y2-b)/x2 (Hinweis: wir übersetzten die Punkte, so dass xi > 0).

Lösung für b gibt

b = (x1y2 - y1x2)/(x1-x2)

(Beachten Sie, wenn x1 = x2, dann P1 und-P2 nicht kollinear mit einem Punkt auf der Y-Achse).

Betrachten |b|.

|b| = |x1y2 - y1x2| /|x1 -x2|

Nun die xmax werden die x-Koordinate des am weitesten rechts liegenden Punkt und ymax die Koordinierung der obersten.

Lassen auch D werden die kleinsten nicht-null-x-Koordinate der Differenz der beiden Punkte (dies existiert, da nicht alle axis identisch sind, da nicht alle Punkte sind kollinear).

Dann haben wir, dass |b| <= xmax*ymax/D.

So, Holen unsere Punkt Q (0,b), so dass |b| > b_0 = xmax*ymax/D

D kann sein gefunden in O(nlogn) Zeit.

Der Größenordnung von b_0 Recht groß und wir vielleicht zu tun haben mit der Genauigkeit Probleme.

Natürlich eine bessere option ist zu wählen Q zufällig! Mit einer Wahrscheinlichkeit von 1, finden Sie den Punkt, den Sie brauchen, so dass die erwartete Laufzeit O(n).

Wenn wir einen Weg finden könnten, um pick-Q in O(n) Zeit (durch die Suche nach einigen anderen Kriterium), dann können wir diesen Algorithmus laufen in O(n) Zeit.

InformationsquelleAutor der Antwort
10
1. Erstellen Sie eine beliebige Zeile in dieser Ebene. Projekt-jeder Punkt auf dieser Linie ein.k.eine für jeden Punkt Holen den nächsten Punkt auf dieser Linie zu diesem Punkt.
2. Damit die Punkte an der Linie in beide Richtungen, und wählen Sie einen Punkt auf dieser Linie, so dass es eine gleiche Anzahl von Punkten auf der Linie in beide Richtungen.
3. Holen Sie sich die Linie, die senkrecht zu der ersten Linie verläuft durch diesen Punkt. Diese Zeile wird noch die Hälfte der ursprünglichen Punkte auf beiden Seiten.
Es gibt einige Fälle zu vermeiden, wenn dies zu tun. Am wichtigsten ist, wenn alle den Punkt sind, sich auf eine einzige Zeile, wählen Sie nicht eine senkrechte Linie, die durchläuft. In der Tat, wählen Sie die Zeile selbst, so dass Sie nicht haben, um sorgen über die Projektion der Punkte. In Bezug auf die tatsächliche Mathematik, die dahinter steckt, Vektor-Projektionen sehr nützlich sein wird.

InformationsquelleAutor der Antwort tlayton
4

Dies ist eine Modifikation Die Aufteilung einer Ebene der Punkte in zwei gleiche Hälften die es ermöglicht für den Fall, dass bei überlappenden Punkte (in dem Fall wird es sagen, ob oder nicht die Antwort ist).
```
If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).
```
Dies ist O(N) im Gegensatz zu anderen vorgeschlagenen Lösungen.

Vorausgesetzt, dass eine Lösung existiert, mit der oben beschriebenen Methode wird wahrscheinlich kündigen, obwohl ich nicht einen Beweis.

Versuchen, den oben beschriebenen Algorithmus ein paar mal, es sei denn, Sie erkennen, überlappende Punkte. Wenn Sie erkennen, eine hohe Anzahl der überlappenden Punkte, die Sie möglicherweise für eine raue Fahrt, aber es ist eine furchtbar ineffiziente brute-force-Lösung, die umfasst die Prüfung aller möglichen Winkel:
```
For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.
```
Einem kritischen Winkel ist definiert als der Winkel, die eventuell das Ergebnis verändern (sich vorstellen, die Lösung auf eine Vorherige Antwort, drehen Sie die gesamte Menge der Punkte, bis einer oder mehrere Punkte tauscht position mit einem oder mehreren anderen Punkte, die überquerung der Trennlinie. Es gibt nur endlich viele von diesen, und ich denke, Sie sind begrenzt durch die Anzahl der Punkte, so sind Sie wahrscheinlich auf der Suche an etwas im Bereich O(N^2)-O(N^2 log(N)) wenn Sie überlappende Punkte, für einen brute-force-Ansatz.

InformationsquelleAutor der Antwort ninjagecko
1

Ich denke, dass eine gute Möglichkeit ist zu Sortieren/Reihenfolge/Reihenfolge der Punkte (z.B. von Links nach rechts), und wählen Sie dann eine Linie, die durchläuft (oder zwischen) den mittleren Punkt[s] in der Sequenz.

InformationsquelleAutor der Antwort ChrisW
1

Gibt es offensichtlich Fälle, in denen keine Lösung möglich ist. E. g. wenn Sie drei Haufen Punkte. Ein Punkt, an Standort A, Zwei Punkte an Ort B und fünf Punkte an Position C.

Wenn Sie erwarten einige menschenwürdigen Verteilung, können Sie wahrscheinlich bekommen, um ein gutes Ergebnis mit tlayton-Algorithmus. Wählen Sie die erste Linie schräg, Sie könnten bestimmen, in welchem Umfang der ganze Punkt zu setzen, und den Winkel wählen, der größten Bildschirmdiagonale.

InformationsquelleAutor der Antwort relet
1

Den median verteilt eine Reihe von zahlen, in der Art und Weise ähnlich zu dem, was Sie versuchen zu erreichen, und es kann berechnet werden, in O(n) Zeit mit einem Auswahl-Algorithmus (das Dokument in Cormen et al ist besser, so möchten Sie vielleicht zu schauen, gibt es stattdessen). So finden Sie den Mittelwert Ihrer x-Werte M_x (oder Ihre y-Werte M_ywenn Sie möchten) und setzen x = M_x (oder y = M_y) und dass die Linie, die Axial ausgerichtet und teilen Sie Ihre Punkte ebenso.

Wenn die Natur des Problems erfordert, dass nicht mehr als ein Punkt liegt auf der Linie (wenn Sie eine ungerade Anzahl von Punkten in Ihrer Gruppe, mindestens einer von Ihnen wird auf der Linie) und entdecken Sie, dass ist, was passiert ist (oder Sie wollen einfach nur, um Schutz vor der Möglichkeit), drehen alle Ihre Punkte von einem zufälligen Winkel, θ und berechnen Sie den Mittelwert der gedrehten Punkte. Sie dann drehen Sie die median-Linie, die Sie berechnet -θ und es wird gleichmäßig aufteilen Punkte.

Die Wahrscheinlichkeit, dass die zufällige Auswahl von θ, so dass das problem manifestiert sich wieder sehr klein, mit einer endlichen Anzahl von Punkten, aber wenn es funktioniert, versuchen Sie es erneut mit unterschiedlichen θ.

InformationsquelleAutor der Antwort andand
0

Weiß ich nicht wie nützlich das ist, die ich gesehen habe ein ähnliches problem...

Wenn Sie bereits den Richtungs Vektor (aka die Koeffizienten der Dimensionen der Ebene).

Dann kann man zwei Punkte innerhalb dieser Ebene, und indem Sie einfach die Mittelpunkt-Formel finden Sie den Mittelpunkt dieser Ebene.

Dann mit dem Koeffizienten, der Ebene und dem Mittelpunkt Sie finden eine Ebene, die gleichen Abstand von den beiden Punkten, unter Verwendung der Allgemeinen Gleichung der Ebene.

Einer Zeile wäre dann zu bilden, die im Ausdruck eine variable, die in Bezug auf die anderen
so würden Sie finden, eine Linie mit gleichem Abstand zwischen den beiden Ebenen.

Gibt es verschiedene Methoden, dies zu tun, wie die Projektion mit Hilfe der Distanz-Gleichung aus einem Flugzeug, aber ich glaube, dass erschweren würden Ihre Mathematik-eine Menge.

InformationsquelleAutor der Antwort user342219
0

Hinzufügen to M ' s Antwort: eine Methode zum erzeugen einer Q (das ist nicht so weit Weg) in O(n log n).

Beginnen mit, lassen Sie F sein alle Punkt auf der y-Achse, dh. Q = (0,b) - eine gute Wahl sein könnte (0,0) oder (0, (y_max-y_min)/2).

Überprüfen Sie nun, wenn es zwei Punkte (x₁y₁), (x₂y₂) kollinear mit Q. Die Linie zwischen jedem Punkt, und Q ist y = mx + b; da b konstant ist, das heißt, zwei Punkte sind kollinear mit Q, wenn Ihre Steigungen m gleich sind. So bestimmen Sie die Steigungen m_i für alle Punkte und prüfen Sie, ob es irgendwelche Duplikate: (amoritized O(n) eine hash-Tabelle)

Wenn alle m ' s unterscheiden, sind wir fertig; wir fanden, Q und M die oben angegebenen Algorithmus erzeugt die Zeile in O(n) Schritte.

Wenn zwei Punkte sind kollinear mit Q, verschieben wir Q nur ein winzigen Betrag ε, Q_neue = (0, b + ε), und zeigen Sie, dass Q_neue - werden nicht kollinear mit zwei anderen Punkte.

Kriterium für ε abgeleitete unten ist:
```
ε < m_minΔ*x_min 
```
Beginnen mit, unsere m ' s wie folgt Aussehen:
```
m_i = y_i/x_i - b/x_i 
```
Finden wir die minimale Differenz zwischen zwei beliebigen verschiedene m_i und nennen es m_minΔ (O(n log n) durch, zum Beispiel, Sortieren, vergleichen Unterschiede zwischen m_i und _i+1 für alle i)

Wenn wir fudge b durch ε, die neue Gleichung für m wird:
```
m_i,neu = y_i/x_i - b/x_i - ε/x_i 
= m_i,alt - ε/x_i 
```
Da ε > 0 und x_i - > 0 ist, werden alle m ' s sind reduziert, und alle sind reduziert auf ein maximum von ε/x_min. Also, wenn
```
ε/x_min < m_minΔie. 
ε < m_minΔ*x_min 
```
wahr ist, dann zwei m_idie zuvor ungleich, wird garantiert bleiben ungleich.

Alles, was übrig ist, um zu zeigen, dass, wenn m_1,alt = m_2,altm_1,neu =/= m_{2 new}. Da sowohl m_i wurden reduziert um einen Betrag ε/x_idies ist äquivalent zu zeigen, x₁ =/= x₂. Wenn Sie wurden gleich, dann:
```
y₁ = m_1,altx₁ + b = m_2,altx₂ + b = y₂ 
```
Widersprechen unserer Annahme, dass alle Punkte sind Verschieden. So, m_{1, neu} =/= m_{2 new}und keine zwei Punkte sind kollinear mit Q.

InformationsquelleAutor der Antwort BlueRaja - Danny Pflughoeft
0

Hier ist, wie ich an dieses problem (mit der Annahme, dass n und auch KEINE drei Punkte sind kollinear):

1) Abholen der Punkt mit der kleinsten Y-Wert. Nennen wir es Punkt P.

2) Nehmen Sie diesen Punkt als den neuen Ursprungs-Punkt, so dass alle anderen Punkte haben positive Y-Werte nach dieser transformation.

3) Für jede andere Stelle (es sind n - 1 Punkte übrig), denke, es unter dem polaren Koordinatensystem. Jeder andere Punkt dargestellt werden kann, mit einem radius und Winkel. Könnten Sie ignorieren den radius und konzentrieren Sie sich nur auf die Winkel.

4) Wie kann man die Zeile finden, teilen Sie die Punkte gleichmäßig? Finde den median von (n - 1) Winkeln. Die Linie von Punkt P zu dem Punkt mit, dass die median-Winkel teilen die Punkte gleichmäßig.

Zeit, die Komplexität dieses Algorithmus ist O(n).

InformationsquelleAutor der Antwort nybon
0

Nahm ich die Idee von Moron und andand und
weiterhin bilden eine deterministische O(n) Algorithmus.

Ich auch davon ausgegangen, dass die Punkte sind deutlich und
n ist auch (dachte der Algorithmus kann
so geändert, dass ungleiche n mit einem Punkt
auf der Trennlinie werden ebenfalls unterstützt).

Versucht der Algorithmus, teilen Sie die Punkte mit einer vertikalen Linie zwischen Ihnen. Dieser schlägt nur, wenn die Punkte in der Mitte haben die gleichen x-Wert. In diesem Fall wird der Algorithmus bestimmt, wie viele Punkte mit den gleichen x-Wert haben, werden auf der linken und unteren Seite und dementsprechend dreht sich die Linie.

Ich werde versuchen zu erklären, mit einem Beispiel.
Lassen Sie uns davon ausgehen, wir haben 16 Punkte auf einer Ebene.
Zunächst müssen wir den Punkt mit der 8. größte x-Wert
und der Punkt mit dem 9. größten x-Wert.
Mit einer Auswahl-Algorithmus möglich ist dies in O(n),
wie schon in einer anderen Antwort.
Wenn der x-Wert der Punkte ist unterschiedlich, wir sind fertig.
Wir erstellen eine vertikale Linie zwischen zwei Punkte und
das teilt die Punkte gleich.

Problematisch ist nun, wenn die x-Werte gleich sind. Wir haben also 3 Mengen von Punkten.
Dass auf der linken Seite (x < x_a), in der Mitte (x = x_a)
und das auf der rechten Seite (x > x_a).
Die Idee ist nun zum zählen der Punkte auf der linken Seite und
berechnen Sie, wie viele Punkte aus der Mitte muss es gehen
so, dass die Hälfte der Punkte sind auf dieser Seite. Wir ignorieren können der rechten Seite hier
denn wenn wir die Hälfte der Punkte auf der linken Seite, die mehr als die Hälfte muss auf der rechten Seite.

Also mal davon ausgehen wir haben 3 Punkte (c=3) auf der linken Seite,
6 in der Mitte und 7 auf der rechten Seite
(der Algorithmus nicht wissen, der Graf, von der Mitte oder auf der rechten Seite,
weil es nicht brauchen, aber wir konnten auch feststellen, es in O(n)).
Wir brauchen 8-3=5 Punkte von der Mitte zu gehen, auf der linken Seite.
Die Punkte, die wir schon im ersten Schritt sind jetzt nutzlos, da
weil Sie nur bestimmt durch den x-Wert
und kann irgendeinen der Punkte in der Mitte.

Wir wollen die 5 Punkte aus der Mitte mit dem niedrigsten y-Wert auf der linken Seite und
der Punkt mit der höchsten y-Wert auf der rechten Seite.
Wieder mit dem Auswahl-Algorithmus, kommen wir auf den Punkt mit dem 5. größten y-Wert
und der Punkt mit der 6. größten y-Wert.
Beide Punkte haben den x-Wert x_a,
sonst würden wir nicht zu diesem Schritt zu bekommen,
weil es wäre eine vertikale Linie.

Nun können wir den Punkt Q in der Mitte der zwei Punkte.
Das ist ein Punkt aus der resultierenden Linie.
Ein weiterer Punkt ist erforderlich, so dass keine Punkte aus der linken oder rechten Seite sind geteilt.
Um diesen Punkt müssen wir den Punkt von der linken Seite,
das hat den niedrigsten Winkel (b_h) zwischen den die vertikale Linie bei x_a
und die Linie bestimmt, die durch diesen Punkt und f:
Wir müssen auch diesen Punkt von der rechten Seite (mit Winkel a_g).
Der neue Punkt R zwischen dem Punkt mit dem unteren Winkel
und einen Punkt auf der vertikalen Linie
(wenn der untere Winkel auf der linken Seite einen Punkt oberhalb von Q
und wenn der untere Winkel auf der rechten Seite einen Punkt unter F).

Die Linie bestimmt durch Q und R trennt die Punkte in der Mitte
so, dass es eine gerade Anzahl von Punkten auf beiden Seiten.
Es nicht teilen, keine Punkte auf der linken oder auf der rechten Seite,
denn wenn er es würde, wäre eine geringere Winkel und
würde wurden gewählt, um zu berechnen, R.

Aus der Sicht eines mathematican, dass sollte gut funktionieren in O(n).
Für computer-Programmen ist es relativ einfach zu finden, ein Fall
wo Präzision zu einem problem. Ein Beispiel mit 4 Punkten wäre
A(0, 100000000), B(0, 100000001), C(0, 0), D(0.0000001, 0).
In diesem Beispiel Q (0, 100000000.5) und R (0.00000005, 0).
Das gibt B und C auf der linken Seite und A und D auf der rechten Seite.
Aber es ist möglich, dass A und B beide auf der Trennlinie,
aufgrund von Rundungsfehlern. Oder vielleicht nur einer von Ihnen.
Damit gehört es zu den input-Werte, wenn dieser Algorithmus passt zu den Anforderungen.
1. bekommen, dass zwei Punkte P_a(x_ay_a) und P_b(x_by_b)
  
  was sind die gemittelten Werte anhand der x-Werte > O(n)
2. wenn x_a != x_b können Sie hier aufhören
  
  weil ein y-Achse parallel zu der Linie zwischen zwei Punkte ist das Ergebnis > O(1)
3. bekommen alle Punkte, wo der Wert x gleich x_a > O(n)
4. zählen Punkte mit x-Wert kleiner als x_a c > O(n)
5. Holen Sie sich den niedrigsten Punkt P_c - basiert auf der y-Werte von Punkten aus 3. > O(n)
6. bekommen, der größte Punkt P_d - basiert auf der y-Werte von Punkten aus 3. > O(n)
7. bekommen die (n/2-c)th größte Punkt P_e - basiert auf der y-Werte von Punkten aus 3. > O(n)
8. auch der nächste größte Punkt P_f - basiert auf der y-Werte von Punkten aus 3. > O(n)
9. erstellen Sie einen neuen Punkt Q (x_ay_e+y_f)/2)
  zwischen P_e und P_f > O(1)
10. für alle Punkte P_i berechnen
  
  der Winkel a_i zwischen P_c, Q und P_i und
  
  der Winkel b_i zwischen P_d, Q und P_i > O(n)
11. den Punkt P_g mit der niedrigsten Winkel a_g (mit_g - >0° und a_g<180°) > O(n)
12. den Punkt P_h mit der niedrigsten Winkel b_h (mit b_h - >0° und b_h<180°) > O(n)
13. wenn es nicht irgendwelche P_g P_h (alle Punkte haben den gleichen x-Wert)
  
  erstellen Sie einen neuen Punkt R (x_a+1, 0), aber irgendwo mit einem anderen x-Wert als x_a
  
  sonst wenn a_g ist niedriger als b_h
  
  erstellen Sie einen neuen Punkt R ((x_c+x_g)/2, (y_c+y_g)/2) zwischen P_c und P_g
  
  sonst
  
  erstellen Sie einen neuen Punkt R ((x_d+x_I)/2, (y_d+y_I)/2) zwischen P_d und P_h > O(1)
14. der Linie bestimmt durch Q und R trennt die Punkte > O(1)
InformationsquelleAutor der Antwort rudi-moore

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.