2010-11-14 7 views
45

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

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

+2

Nie myśl, że to możliwe. Byłoby możliwe, gdyby istniała taka transformacja w jednym punkcie, który mógłby pomóc, ale niestety każda transformacja, o której myślę, wymaga 2 punktów. Podejście probabilistyczne (takie jak Monte Carlo) może być szybsze, ale nie byłoby gwarancji, że znajdzie maksimum. – ruslik

+0

Jeśli podmienisz współrzędne punktu na równanie liniowe, 'k * x [i] + b = y [i]', otrzymasz równanie dotyczące 'k' i' x'. W {K, x} -space będzie to linia. Staje się więc problemem maksymalnych linii przechodzących przez jeden punkt. Może mieć rozwiązanie. – Vovanium

+1

Zauważ, że problem ma sens tylko w przypadku coodonatów całkowitych, więc 'k' i' b' muszą być liczbami wymiernymi, takimi że 'b == y - k * x', gdzie' y' i 'x' są liczbami całkowitymi. Być może poprzez przekształcenie problemu w formie "znajdź takie wymierne liczby" b "i" k ", które spełniają większość równań" pomożemy. – ruslik

Odpowiedz

37

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.

+2

Dobra odpowiedź. Poprosiłem o to w wywiadzie, dałem odpowiedź O (n^2) i poczułem się źle. Twoja odpowiedź spowodowała, że ​​odszedłem od:: (->: D –

+1

Co jest takiego szczególnego w przyjmowaniu punktów jako (x, x^3)? Dlaczego matematyka nie działa, powiedzmy (x, x^2)? – gjain

+0

Miałem właśnie zapytać o to, jakie gwarancje, że punkt przecięcia z osią y jest również taki sam dla tych 3 linii (tj. Odpowiedź pokazuje tylko, że * nachylenie * będzie takie samo), ale potem kliknęło: jeśli dwie linie mają to samo nachylenie * i przechodzenie przez jakiś wspólny punkt *, wtedy są one koniecznie tą samą linią - i tak jest w przypadku wszystkich 3 możliwych linii tutaj (xy i xz mają to samo nachylenie i dzielą x, a yz ma to samo nachylenie i akcje z z xz). –

4

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.

+4

W rzeczywistości, jeśli ograniczysz problem do linii przechodzących przez punkt początkowy (0,0), można go rozwiązać w czasie O (n), używając skrótu. –

-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

+0

Ale to wciąż O (n^2) i jest bardziej skomplikowane w implementacji niż metoda OP. –

+0

przejdziesz przez każdy punkt jeden raz, czyli jeden n, to musisz posortować i policzyć te same punkty kątowe, czy to jest uważane za kolejne n? Nie jestem tego pewien, proszę, przepraszam. –

+0

w 1. "dla każdego punktu" "dla wszystkich pozostałych punktów", oznacza zastosowanie operatora w punktach 'n-1'' n' razy. To jest O (n^2). –

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.

0

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

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

Powiązane problemy