L’obiettivo primario della ricerca in geometria computazionale combinatoria è quello di sviluppare algoritmi efficienti e strutture di dati per risolvere problemi enunciati in termini di oggetti geometrici di base: punti, segmenti di linea, poligoni, poliedri, ecc.
Alcuni di questi problemi sembrano così semplici che non sono stati considerati come problemi fino all’avvento dei computer. Consideriamo, per esempio, il problema della coppia più vicina:
- Dati n punti nel piano, trova i due con la distanza minore tra loro.
Si potrebbero calcolare le distanze tra tutte le coppie di punti, che sono n(n-1)/2, poi scegliere la coppia con la distanza minore. Questo algoritmo di forza bruta richiede tempo O(n2), cioè il suo tempo di esecuzione è proporzionale al quadrato del numero di punti. Un risultato classico della geometria computazionale è stata la formulazione di un algoritmo che richiede O(n log n). Sono stati scoperti anche algoritmi randomizzati che impiegano O(n) tempo atteso, così come un algoritmo deterministico che impiega O(n log n) tempo.
Classi di problemiModifica
I problemi fondamentali della geometria computazionale possono essere classificati in diversi modi, secondo vari criteri. Si possono distinguere le seguenti classi generali.
Problemi staticiModifica
Nei problemi di questa categoria, viene dato qualche input e l’output corrispondente deve essere costruito o trovato. Alcuni problemi fondamentali di questo tipo sono:
- Carena convessa: Dato un insieme di punti, trovare il più piccolo poliedro/poligono convesso contenente tutti i punti.
- Intersezione di segmenti di linea: Trova le intersezioni tra un dato insieme di segmenti di linea.
- Triangolazione di Delaunay
- Diagramma di Voronoi: Dato un insieme di punti, partizionare lo spazio in base a quali punti sono più vicini ai punti dati.
- Programmazione lineare
- Coppia di punti più vicini: Dato un insieme di punti, trova i due con la più piccola distanza l’uno dall’altro.
- Coppia di punti più lontani
- Cerchio vuoto più grande: Dato un insieme di punti, trova un cerchio più grande con il suo centro all’interno del loro scafo convesso e che non racchiuda nessuno di loro.
- Percorso più breve euclideo: Collegare due punti in uno spazio euclideo (con ostacoli poliedrici) mediante un percorso più breve.
- Triangolazione di poligoni: Dato un poligono, partizionare il suo interno in triangoli
- Generazione di mesh
- Operazioni booleane sui poligoni
La complessità computazionale per questa classe di problemi è stimata dal tempo e dallo spazio (memoria del computer) richiesti per risolvere una data istanza del problema.
Problemi di interrogazione geometricaModifica
Nei problemi di interrogazione geometrica, comunemente noti come problemi di ricerca geometrica, l’input consiste di due parti: la parte dello spazio di ricerca e la parte di interrogazione, che varia sulle istanze del problema. Lo spazio di ricerca ha tipicamente bisogno di essere preprocessato, in modo che si possa rispondere in modo efficiente a più richieste.
Alcuni problemi fondamentali di ricerca geometrica sono:
- Ricerca per intervallo: preprocessare un insieme di punti, al fine di contare in modo efficiente il numero di punti all’interno di una regione di ricerca.
- Localizzazione di punti: Dato un partizionamento dello spazio in celle, produrre una struttura di dati che dica in modo efficiente in quale cella si trova un punto da interrogare.
- Vicino più vicino: Preprocessare un insieme di punti, al fine di trovare in modo efficiente quale punto è più vicino ad un punto di interrogazione.
- Ray tracing: Dato un insieme di oggetti nello spazio, produrre una struttura di dati che dica in modo efficiente quale oggetto un raggio di ricerca interseca per primo.
Se lo spazio di ricerca è fisso, la complessità computazionale per questa classe di problemi è solitamente stimata da:
- il tempo e lo spazio richiesti per costruire la struttura di dati da cercare in
- il tempo (e talvolta uno spazio extra) per rispondere alle query.
Per il caso in cui lo spazio di ricerca può variare, vedi “Problemi dinamici”.
Problemi dinamiciModifica
Un’altra grande classe è quella dei problemi dinamici, in cui l’obiettivo è trovare un algoritmo efficiente per trovare una soluzione ripetutamente dopo ogni modifica incrementale dei dati di input (aggiunta o cancellazione di elementi geometrici). Gli algoritmi per problemi di questo tipo tipicamente coinvolgono strutture dati dinamiche. Qualsiasi problema geometrico computazionale può essere convertito in uno dinamico, al costo di un maggiore tempo di elaborazione. Per esempio, il problema della ricerca della gamma può essere convertito nel problema della ricerca dinamica della gamma prevedendo l’aggiunta e/o la cancellazione dei punti. Il problema della carena convessa dinamica consiste nel tenere traccia della carena convessa, ad esempio, per l’insieme di punti che cambia dinamicamente, cioè, mentre i punti in ingresso vengono inseriti o cancellati.
La complessità computazionale per questa classe di problemi è stimata da:
- il tempo e lo spazio necessari per costruire la struttura di dati da cercare in
- il tempo e lo spazio per modificare la struttura di dati cercata dopo un cambiamento incrementale nello spazio di ricerca
- il tempo (e talvolta uno spazio extra) per rispondere a una query.
VariazioniModifica
Alcuni problemi possono essere trattati come appartenenti a una delle due categorie, a seconda del contesto. Per esempio, considerate il seguente problema.
- Punto in un poligono: Decidere se un punto è dentro o fuori un dato poligono.
In molte applicazioni questo problema è trattato come un problema a colpo singolo, cioè appartenente alla prima classe. Per esempio, in molte applicazioni di computer grafica un problema comune è trovare quale area sullo schermo è cliccata da un puntatore. Tuttavia, in alcune applicazioni, il poligono in questione è invariante, mentre il punto rappresenta una query. Per esempio, il poligono di input può rappresentare un confine di un paese e un punto è una posizione di un aereo, e il problema è determinare se l’aereo ha violato il confine. Infine, nell’esempio già citato della computer grafica, nelle applicazioni CAD i dati di input che cambiano sono spesso memorizzati in strutture dati dinamiche, che possono essere sfruttate per accelerare le interrogazioni punto-poligono.
In alcuni contesti di problemi di interrogazione ci sono aspettative ragionevoli sulla sequenza delle interrogazioni, che possono essere sfruttate sia per strutture dati efficienti che per stime di complessità computazionale più severe. Per esempio, in alcuni casi è importante conoscere il caso peggiore per il tempo totale per l’intera sequenza di N query, piuttosto che per una singola query. Vedi anche “analisi ammortizzata”.