Intersezioni cerchio di calcolo in O ((n + s) log n)

Question

Sto cercando di capire come progettare un algoritmo in grado di completare questa attività con una complessità di O ((n + s log n). s è la quantità di intersezioni. Ho provato a cercare su internet, ma non ho trovato davvero qualcosa.

In ogni caso, mi rendo conto che avere una buona struttura dati è la chiave qui. Sto usando un'implementazione Red Black Tree in java: TreeMap. Io uso anche il famoso (?) Sweep-line algoritmo per aiutarmi ad affrontare il mio problema.

Lasciatemi spiegare prima la configurazione.

Ho un programmatore. Questo è un PriorityQueue con le mie cerchie ordinate (in ordine crescente) in base alla loro coordinata più a sinistra. scheduler.next() fondamentalmente esegue il polling di PriorityQueue, restituendo la prossima cerchia più a sinistra.

public Circle next() 
{ return this.pq.poll(); } 

Ho anche un array con 4n punti evento qui. Garantire ad ogni cerchio ha 2 punti evento: la maggior parte sinistra x e la maggior parte destra x. Lo scheduler ha un metodo sweepline() per ottenere il prossimo evento.

public Double sweepline() 
{ return this.schedule[pointer++]; } 

Ho anche uno stato. Lo stato della linea di scorrimento è più preciso. Secondo la teoria, lo stato contiene i cerchi che possono essere confrontati l'uno con l'altro. Il punto di avere la linea di tendenza in questa storia è che sei in grado di escludere molti candidati perché semplicemente non sono nel raggio delle cerchie attuali.

Ho implementato lo stato con un TreeMap<Double, Circle>. Doppio è il circle.getMostLeftCoord().

Questa TreeMap garantisce O (log n) per inserimento/rimozione/ricerca.

lo stesso algoritmo è implementato in questo modo:

Double sweepLine = scheduler.sweepline(); 
Circle c = null; 
while (notDone){ 
    while((!scheduler.isEmpty()) && (c = scheduler.next()).getMostLeftCoord() >= sweepLine) 
     status.add(c); 


    /* 
    * Delete the oldest circles that the sweepline has left behind 
    */ 
    while(status.oldestCircle().getMostRightCoord() < sweepLine) 
     status.deleteOldest(); 

    Circle otherCircle; 
    for(Map.Entry<Double, Circle> entry: status.keys()){ 
     otherCircle = entry.getValue(); 
     if(!c.equals(otherCircle)){ 
      Intersection[] is = Solver.findIntersection(c, otherCircle); 
      if(is != null) 
       for(Intersection intersection: is) 
        intersections.add(intersection); 
     } 
    } 

    sweepLine = scheduler.sweepline(); 
} 

EDIT: Solver.findIntersection(c, otherCircle); rendimenti max 2 punti di intersezione. Non si considera che cerchi sovrapposti abbiano intersezioni.

Il codice del SweepLineStatus

public class BetterSweepLineStatus { 

TreeMap<Double, Circle> status = new TreeMap<Double, Circle>(); 

public void add(Circle c) 
{ this.status.put(c.getMostLeftCoord(), c);  } 

public void deleteOldest() 
{ this.status.remove(status.firstKey()); } 

public TreeMap<Double, Circle> circles() 
{ return this.status;  } 

public Set<Entry<Double, Circle>> keys() 
{ return this.status.entrySet(); } 

public Circle oldestCircle() 
{ return this.status.get(this.status.firstKey()); } 

ho provato il mio programma, e ho dovuto chiaramente O (n^2) la complessità. Cosa mi manca qui? Qualsiasi input che voi ragazzi potreste essere in grado di fornire è più che benvenuto.

Grazie in anticipo!

Answer 1

Non è possibile trovare tutti i punti di intersezione di n cerchi nel piano in O(n log n) tempo perché ogni coppia di cerchi può avere fino a due punti di intersezione distinti e quindi n circoli può avere fino a n² - n punti di intersezione distinti e quindi non ci riesce essere elencato nel tempo O(n log n).

Un modo per ottenere il massimo numero di punti di intersezione n² - n è posizionare i centri di n cerchi di raggio uguale a r reciprocamente diversi punti di una linea di lunghezza l < 2r.

Answer 2

N cerchi con lo stesso centro e raggio avranno N (N-1)/2 coppie di cerchi che si intersecano, mentre usando cerchi abbastanza grandi in modo che i loro confini siano linee quasi diritte è possibile disegnare una griglia con N/2 linee che intersecano ciascuna delle linee N/2, che è nuovamente N^2. Vorrei vedere e vedere quante voci sono in genere presenti nella mappa quando aggiungi una nuova cerchia.

Si potrebbe provare a utilizzare i quadrati di delimitazione delle proprie cerchie e mantenere un indice sui quadrati in sospeso in modo da poter trovare solo i quadrati che hanno coordinate y che intersecano il quadrato della query (presupponendo che la linea di scorrimento sia parallela alla asse). Ciò significherebbe che, se i tuoi dati fossero amichevoli, potresti tenere un sacco di quadrati in sospeso e controllarne solo alcuni per le possibili intersezioni dei cerchi all'interno dei quadrati. Dati abbastanza ostili da causare intersezioni N^2 reali costituiranno sempre un problema.

Answer 3

Quanto sono grandi i cerchi rispetto a tutta l'area? Se il rapporto è abbastanza piccolo, prenderei in considerazione l'idea di metterli in secchi di qualche tipo. Renderà la complessità un po 'più complicata di O(n log n) ma dovrebbe essere più veloce.