Come si determina se è possibile disegnare un cerchio attorno a un insieme di punti, in modo che i punti dell'altro set non siano al suo interno?

Question

Mi sto interrogando su un algoritmo che restituisce vero o falso, dicendomi se è possibile tracciare un cerchio attorno a un insieme di punti A, in modo tale che qualsiasi punto dall'insieme di punti B non sia al suo interno, o viceversa (possibile disegnare un cerchio attorno a un insieme di punti B, in modo tale che qualsiasi punto dall'insieme di punti A non sia al suo interno).

In pratica, vengono forniti 2 insiemi di punti come input e occorre determinare se è possibile disegnare un cerchio attorno a uno di essi, in modo tale che qualsiasi punto dell'altro non sia all'interno di esso.

Ho visto Megiddo's linear time algorithm per il smallest enclosing circle problem, ma il problema è che disegna solo il cerchio più piccolo, il che significa che non funziona nel caso in cui sia necessaria una circonferenza grande.

Ecco una foto di quello che voglio dire:

In questa immagine è possibile disegnare un grande cerchio intorno al set di punti rossi, in modo che uno qualsiasi dei punti verdi non sono al suo interno, quindi l'algoritmo di Megiddo non funzionerà.

Answer 1

In questo lavoro, riduciamo rilevare se due insiemi di punti nel piano possono essere separati da un cerchio, a separabilità lineare di punti in 3D:

O'Rourke, Joseph, S Rao Kosaraju e Nimrod Megiddo. "Calcolare la separabilità circolare." Discreta & Geometria computazionale, .1 (1986): 105-113. (PDF download.)

Answer 2

Se si testano molti potenziali punti centrali (ad esempio su una griglia), quindi per ogni punto la distanza maggiore rispetto a qualsiasi punto rosso dovrebbe essere inferiore alla distanza minima rispetto a qualsiasi punto verde, al fine di avere un cerchio che contiene solo punti rossi e nessun punto verde.

Immagino che iniziando con una griglia sparsa e monitorando i valori "distanza maggiore rispetto a qualsiasi punto rosso", "distanza più piccola rispetto a qualsiasi punto verde", è possibile rendere le aree promettenti più sottili e precise (sezioni intelligenti) per catturare finalmente un punto o un'area con la proprietà desiderata.

Si potrebbe anche essere in grado di utilizzare alcune derivate, come andare nella direzione in cui il rapporto tra "distanza maggiore da qualsiasi punto rosso" a "distanza minima da qualsiasi punto verde" diminuisce più rapidamente. D'altra parte il problema potrebbe essere non convesso e la convergenza potrebbe non essere garantita.

Answer 3

Provare questo: utilizzare stereographic projection per proiettare i punti su una sfera. Quindi devi trovare un piano che passa attraverso la sfera che taglia la sfera in modo che tutti i punti del primo set si trovino su un lato del piano e tutti i punti nel secondo set si trovino sull'altro lato del piano. L'intersezione tra il piano e la sfera è un cerchio, che si ricollega a un cerchio (o in rare circostanze, una linea) sul piano originale. Il cerchio risultante sul piano originale ha le proprietà che desideri.

Cambiare il problema da uno su cerchi sul piano a uno su piani in tre dimensioni (oggetti lineari) significa che è possibile utilizzare idee dalla programmazione lineare e dai set convessi per aiutare. Un approccio è quello di utilizzare il hyperplane separation theorem per dimostrare che si può trovare un aereo che separa le immagini delle famiglie dei punti se e solo se gli scafi convesse delle immagini di punti in A e B non si intersecano.

Ci sono molti metodi veloci in hardware e software per determinare se due corpi convessi si intersecano: è il problema di rilevamento delle collisioni, importante nei videogiochi per esempio. Molto lavoro è stato fatto su questo problema (si veda, per esempio, https://www.medien.ifi.lmu.de/lehre/ss10/ps/Ausarbeitung_Beispiel.pdf, che sostiene che l'algoritmo viene eseguito in O (n time)) e non v'è il codice sicuramente liberamente disponibile.

In sintesi: mappare i punti (X, Y) sulla sfera unitaria (x, y, z) con stereografica proiezione proposta dalla formula

(x,y,z) = (2*X/(R^2+1), 2*Y/(R^2+1), (R^2-1)/(R^2+1)), R^2 = X^2+Y^2 

Quindi utilizzare l'algoritmo Gilbert-Johnson-Keerthi o qualche altro algoritmo di rivelazione di collisione per determinare se lo scafo convesso delle immagini di punti in un insieme è disgiunto dallo scafo convesso delle immagini di punti nell'altro insieme. Questo risponde alla domanda se il cerchio esiste. Per trovare effettivamente il cerchio, è necessario un piano di separazione tra i due corpi convessi, che poi si intersecano con la sfera per ottenere un cerchio sulla sfera, che si ricollega al piano dall'inverso della proiezione stereografica.

Se ho capito bene, quanto sopra può essere realizzato in tempo O (n).

Answer 4

Solo un'idea: prendere tutte le coppie di puntini rossi e verdi.

Per ciascuna coppia, calcolare la linea centrale ortogonale.

Questi punti sulla linea sono i punti, dove la distanza dal punto verde e rosso è uguale, quindi un cerchio con questo come centro non avrebbe senso.

Ma l'area sullo stesso lato della linea in cui il punto rosso è anche l'area, dove si trova un potenziale punto centrale.

Per ogni coppia {rosso, verde}, si otterrà una linea e un'area, dove il punto centrale del cerchio sarebbe.

Se intersechi tutte le aree di tutte le coppie, otterrai tutti i potenziali punti centrali per tutte le cerchie.

Nel tuo esempio prendi i due punti verde e il punto rosso tra di loro. Otterrai due linee a 1/2 della distanza sinistra e destra dell'asse verticale.

Prendi il punto verde a sinistra e tutti quelli rossi, otterrai linee da in alto a sinistra a in basso a destra e il centro del cerchio sarà sopra di loro.

Il punto verde corretto con quelli rossi farà lo stesso. Quindi in questo caso si ottiene un'area dei risultati (poligono) che non è troppo lontana dall'asse verticale e almeno una certa distanza sopra l'asse orizzontale e si estende all'infinito.

Per un'altra serie di punti di intersezione potrebbe portare a un insieme vuoto, il che significa che non è possibile tracciare un tale cerchio intorno quelle rosse senza prendere alcune di quelle verdi.

Questo sarà sempre calcolare il risultato corretto ma non ne ho idea, quanto è buona la performance rispetto all'algoritmo di Joseph. Forse può dare un'occhiata?