Jaki jest najskuteczniejszy algorytm znajdowania prostej, która przechodzi przez większość punktów?

Question

Problem:

N punktów podano na dwuwymiarowej płaszczyźnie. Jaka jest maksymalna liczba punktów na tej samej linii prosto?

Problem ma rozwiązanie O (N): przejdź przez każdy punkt i znajdź liczbę punktów, które mają ten sam dx/dy w stosunku do bieżącego punktu. Przechowuj relacje dx/dy w mapie mieszania dla zwiększenia wydajności.

Czy istnieje lepsze rozwiązanie tego problemu niż O (N)?

Answer 1

Jest prawdopodobne, nie rozwiązuje tego problemu, jest znacznie lepszy niż w O (N^2) w standardowym modelu obliczania .

Problem znalezienia trzech współliniowych punktów redukuje problem znalezienia linii przechodzącej przez większość punktów, a znalezienie trzech współliniowych punktów jest 3-SUMA-trudne, co oznacza, że ​​rozwiązanie to w czasie krótszym niż O (n^2) byłby poważnym wynikiem teoretycznym.

Zobacz previous question na znalezienie trzech współliniowych punktów.

Dla twojego odniesienia (używając znanego dowodu), załóżmy, że chcemy odpowiedzieć na problem 3SUM, taki jak znalezienie x, y, z na liście X tak, że x + y + z = 0. Gdybyśmy mieli szybki algorytm dla problem z współliniowym punktem, możemy użyć tego algorytmu, aby rozwiązać problem 3SUM w następujący sposób.

Dla każdego x w X utwórz punkt (x, x^3) (na razie zakładamy, że elementy X są różne). Następnie sprawdź, czy istnieją trzy współliniowe punkty spośród utworzonych punktów.

zauważyć, że ta działa zauważyć, że gdy x + y + z = 0, wówczas nachylenie linii od x do y wynosi

(r^3 - x^3)/(Y - X) = r^2 + yx + x^2

i nachylenie linii od x do z jest

(z - x^3^3)/(ZX) = 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

Odwrotnie, jeśli nachylenie od x do y jest równe nachyleniu od Xt oz następnie

Y^2 + yx + x^2 = Z^2 + zx + x^2

co oznacza, że ​​

(Y -) (X + Y + Z) = 0,

Tak więc albo y = z lub z = -x - y wystarczy, aby udowodnić, że redukcja jest ważna.

Jeśli są duplikaty w X, najpierw sprawdź, czy x + 2y = 0 dla dowolnego x i zduplikowanego elementu y (w czasie liniowym, używając skrótu lub czasu O (n lg n), używając sortowania), a następnie usuń duplikaty przed zmniejszeniem do współliniowego problemu ze znalezieniem punktu.

Answer 2

Jeśli ograniczysz problem do linii przechodzących przez punkt początkowy, możesz zamienić punkty na współrzędne biegunowe (kąt, odległość od początku) i posortować je według kąta. Wszystkie punkty o tym samym kącie leżą na tej samej linii. O (n logn)

Nie sądzę, że istnieje szybsze rozwiązanie w ogólnym przypadku.

Answer 3

Nie jest to rozwiązanie lepsze niż O (N^2), ale można wykonać następujące,

1. Dla każdego punktu przekształcić najpierw przekształcić tak, jakby to, gdzie w (0,0) koordynuje , a następnie wykonaj równoważne tłumaczenie dla wszystkich pozostałych punktów, przesuwając je o taką samą odległość x, y, jaka była potrzebna do przesunięcia oryginalnego wybranego punktu.

2. Przetransformuj nowy zestaw przetłumaczonych punktów pod kątem względem nowego (0,0).

3. Zachowaj zapisaną maksymalną liczbę punktów (MSN) w każdym kącie.

4.Wybierz maksymalnej przechowywanej liczby (MSN) i że będzie rozwiązaniem

Answer 4

Urządzenie Hough Transform może dostarczyć przybliżonego rozwiązania. Jest to przybliżone, ponieważ technika binning ma ograniczoną rozdzielczość w przestrzeni parametrów, więc maksymalny bin daje ci pewien ograniczony zakres możliwych linii.

Answer 5

jest mało prawdopodobne, a $ o (n^2) $ algorytmu istnieje, ponieważ problem (parzystych sprawdzenie czy trzy punkty R^2 są współliniowe), jest 3Sum twardy (http://en.wikipedia.org/wiki/3SUM)

Answer 6

Ponownie rozwiązanie O (n^2) z pseudo kodem. Idea jest tworzona jako tablica asocjacyjna z samą linią jako kluczem. Linia definiowana jest przez nachylenie między dwoma punktami, punkt, w którym linia przecina oś x, a punkt, w którym linia przecina oś y.

Rozwiązanie zakłada stosowanie języków takich jak Java, C# gdzie metoda równań i metod kodu pasmowego obiektu jest używana do funkcji mieszania.

utworzyć obiekt (wezwanie SlopeObject) z 3 pól

1. Slope // Może być Nieskończoność
2. Punkt przecięcia z osią x - poix // Będzie (Nieskończoność, jakaś wartość y) lub (wartość x, 0)
3. Liczba

poix będzie punkt (x, y), parę. Jeśli linia przecina oś X, pojawi się poix (pewna liczba, 0). Jeśli linia jest równoległa do osi x, to poix = (nieskończoność, pewna liczba), gdzie wartość y jest tam, gdzie linia przecina oś y. Przesłonięcie równa się metodzie, w której 2 obiekty są równe, jeśli Slope i poix są równe.

Hashcode jest nadpisywane funkcją, która zapewnia kod bazujący na kombinacji wartości Slope i poix.Niektóre pseudokod poniżej

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); 

Answer 7

Jak już wspomniano, istnieje prawdopodobnie nie jest sposobem rozwiązania ogólnym przypadku tego problemu lepszej niż O (N^2). Jeśli jednak przyjmiesz, że duża liczba punktów leży na tej samej linii (powiedz prawdopodobieństwo, że losowy punkt w zestawie punktów leży na linii z maksymalną liczbą punktów to p) i nie potrzebujesz dokładnego algorytmu, losowy algorytm jest bardziej wydajny.

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) 

Należy zauważyć, że w pierwszym etapie, jeśli wybrał 2 punkty, które leży na linii z maksymalną liczbą punktów, dostaniesz optymalne rozwiązanie. Zakładając, że n jest bardzo duże (tzn. Możemy liczyć z prawdopodobieństwem znalezienia 2 pożądanych punktów jako próbkowanie z wymianą), prawdopodobieństwo takiego zdarzenia wynosi p^2. Dlatego prawdopodobieństwo znalezienia nieoptymalnego rozwiązania po kizotacjach wynosi (1 - p^2)^k.

Załóżmy, że można tolerować fałszywie ujemny wskaźnik szybkości = błąd. Następnie ten algorytm działa w O (nk) = O (n * log (err)/log (1 - p^2)). Jeśli zarówno n jak i p są wystarczająco duże, jest to znacznie bardziej wydajne niż O (n^2). Przypuszczalnie n = 1 000 000 i wiesz, że istnieje co najmniej 10 000 punktów, które leżą w tej samej linii, a następnie n^2 wymagałby operacji o wartości 10^12, podczas gdy randomizowany algorytm wymagałby operacji o wartości 10^9. aby uzyskać poziom błędu mniejszy niż 5 * 10^-5.)