Qual è il miglior algoritmo per trovare se tre punti sono collineari in un insieme di punti dire n. Per favore, spiega anche la complessità se non è banale.Dato un insieme di punti, trova se uno qualsiasi dei tre punti è collineare
Grazie
Bala
Se riesci a trovare un algoritmo migliore di O (N^2), puoi pubblicarlo!
Questo problema è 3-SUM Hard e se esiste un algoritmo sub-quadratico (cioè migliore di O (N^2)) è un problema aperto. Molti comuni problemi di geometria computazionale (compresa la tua) hanno dimostrato di essere 3SUM e questa classe di problemi sta crescendo. Come NP-Hardness, il concetto di 3SUM-Hardness si è dimostrato utile nel dimostrare la "resistenza" di alcuni problemi.
Per una prova che il vostro problema è 3sum duro, si riferiscono alla carta Surver eccellente qui: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf
Il tuo problema sembra a pagina 3 (opportunamente chiamato a 3 punti-ON-LINE) nel documento di cui sopra.
Quindi, l'algoritmo attualmente più noto è O (N^2) ed è già in possesso :-)
Grazie @Moron. Il collegamento è stato molto utile. – Boolean
@Moron - c'è un algoritmo con tempo 'O (n^2)' che non sta usando la tabella hash come quella descritta da @Strilanc? –
@Elazar: Credo che sia possibile, considerando il doppio in cui le linee si mappano ai punti e viceversa (a, b) <-> y = ax + b. Ora il problema corrisponde alla ricerca di vertici nel duale con un grado almeno di 6. Apparentemente questo è possibile nel tempo O (n^2) e nello spazio O (n^2). Questo libro: http://books.google.com/books?id=PBRJ-ruwOQcC ne parla a pagina 94. –
Un semplice O (d * N^2) il tempo e l'algoritmo spazio, dove d è la dimensionalità e N è il numero di punti (probabilmente non ottimale):
La tua condizione è necessaria, ma è sufficiente? Metti 4 punti a (0,0), (0,1), (1,0) e (1,1) per definire il riquadro di delimitazione. La coppia [(0.5.0.6), (0.5.0.7)] crea un segmento che interseca la casella in (0.5,0), così come la coppia [(0.4.0.1), (0.3.0.2)]. Eppure non ci sono tre degli 8 punti su una linea comune. – Eric
È una condizione sufficiente perché due punti definiscono una linea. Hai considerato solo uno dei punti nella coppia di punti di scontro; l'altro sarà diverso, quindi la coppia non corrisponde. –
Giusto. Potresti voler dare maggiori dettagli, nel passaggio 2, per chiarire che i due punti di collisione sono messi insieme per creare una "coppia di collisione". Altrimenti un lettore può confondere la coppia (di punti di collisione) nel passo 3 con la coppia (di punti originali) nel passo 2, come ho fatto io. – Eric
Un'altra soluzione semplice (forse anche banale) che non usa una tabella hash, viene eseguito in O (n log n), e utilizza o (n) spazio:
Diamo S essere un insieme di punti, descriveremo un algoritmo che scopre se S contiene circa tre punti allineati.
o in S do:
Lx -axis attraverso o.S sotto L, con la sua riflessione. (Ad esempio se L è l'asse x, (a,-x) per x>0 diventerà (a,x) dopo la riflessione).Lasciare che la nuova serie di punti sia S'p in S', è l'angolo retto del segmento po con la linea L. Cerchiamo di ordinare i punti S' dai loro angoli.S'. Se ci sono due punti consecutivi che sono collineari con o - return true.Il ciclo esegue n volte e ogni iterazione esegue i passi nlog n. Non è difficile dimostrare che se ci sono tre punti su una linea saranno trovati, e non troveremo nulla altrimenti.
Hai solo bisogno di fare il ciclo esterno per metà dei punti: quelli con il più grande 'y' valori coordinati, corretto? Anche quando hai detto "ci sono due punti consecutivi che sono collineari", in realtà intendevi "ci sono due punti consecutivi che sono collineari insieme al punto' o' ", ti sto capendo correttamente? –
La prima osservazione è corretta, sebbene non cambi la complessità. Fare così per l'altra metà dei punti è equivalente a causa della simmetria. Nota che devi prima ordinarli, il che rende l'algoritmo un po 'più complesso. Anche il secondo punto è corretto, risolvendolo, Grazie. –
È questo il tuo compito? – WhirlWind
Questa domanda è stata discussa in classe e conosco l'algoritmo O (N^2). Ho trovato un algoritmo abbastanza semplice per farlo in O (N^2). Voglio sapere se esiste un algoritmo ancora più semplice. – Boolean
Sono questi 2 punti? –