Dato un cerchio con N definita punti e un punto M fuori del cerchio, trovare il punto che è più vicino a M tra l'insieme di N. O (logN)

Question

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

Ho cercato di trovare una soluzione a questo problema. Ma non ho avuto successo .. Qualcuno può darmi un suggerimento su come procedere con questo problema.

Prenderò 2 coppie di due punti ciascuna. Cioè, farò 2 accordi. Scopri la loro bisettrice perpendicolare. Usando queste bisettrici, scoprirò il centro del cerchio ...

Inoltre, troverò l'equazione del cerchio. E trova il punto di intersezione del punto M con il cerchio ... Questo dovrebbe essere il punto più vicino. Tuttavia, quel punto può o non può esistere nel set di N punti

Grazie.

Answer 1

Supponendo che i punti sulla circonferenza del cerchio siano "in ordine" (cioè ordinati per angolo attorno al centro del cerchio) è possibile utilizzare una ricerca binaria basata su angolo, che dovrebbe raggiungere i limiti O(log(n)).

1. calcolare l'angolo A dal punto M al centro del cerchio - O(1).
2. Utilizzare la ricerca binaria per trovare il punto I sulla circonferenza con angolo maggiore inferiore a A - O(log(n)).
3. Poiché i cerchi sono convessi, il punto più vicino a M è I o I+1. Calcola la distanza per entrambi e prendi il minimo - O(1).

Answer 2

Per trovare un punto più vicino a M, è necessario eliminare i punti binari in base ai tagli planari. È necessario un po 'di pre-elaborazione dei punti di input, dopo di che possiamo trovare un punto più vicino a un dato punto M in O (lgn).

1. Calcolare (se non indicato) rappresentazione polare dei punti in formato (r, θ), dove r è la distanza dal centro e θ è l'angolo di asse x nell'intervallo (-180.180].
2. in ordine tutti N punti in ordine crescente di loro angolo di asse x.

noti che semplice motore di ricerca binaria di un punto più vicino a M non funzionerà qui, ad esempio,

• se i punti dati sono ordinato in modo tale che θ = (-130, -100 , -90, -23, -15,0,2,14,170), quindi per un punto M con θ = -170, la ricerca binaria darà -130 (40 gradi di distanza) come il punto più vicino mentre 170 (20 gradi di distanza) è il punto più vicino a M.
• se ignoriamo il segno mentre ordiniamo (pensando che produrrà output corretto), il nostro nuovo array ordinato sarà simile a θ = (0,2,14,15,23,90,100,130,170), la ricerca binaria per un punto M con θ = -6 produrrà il risultato dovrebbe essere 2 o 14 mentre 0 è il punto più vicino a M in questo caso.

Per eseguire l'operazione di ricerca con tagli planari,

• Find linea planare di taglio passante per il centro del cerchio e perpendicolare alla linea che collega il centro del cerchio con punto M.
• Eliminare metà del piano circolare [90 + θ, -90 + θ) o [-90 + θ, 90 + θ) a seconda di in quale metà del piano M si trova.
• Effettuare tagli planari paralleli al primo taglio e passare attraverso il punto al centro del piano precedente ed eliminare tutti i punti nella metà del piano più lontano da M finché non ci sono più punti nella metà più vicina dell'aereo, in tal caso eliminare la metà più vicina dell'aereo.
• Continuate a tagliare gli aerei finché non restiamo con un punto. Quel punto è il punto più vicino a M. L'operazione totale richiede passi O (lgn).

In caso il dato è inclinata e non uniformemente distribuita nel cerchio, possiamo ottimizzare i tagli planari tale che ogni taglio passa attraverso la mediana (in base all'angolo) di quei punti che vengono lasciati nell'operazione di ricerca.