Algoritmo di Scafo Convesso Dinamico sublinale ma semplice?

Question

Ho bisogno di risolvere il problema dell'algoritmo convex dinamico, ovvero mantenendo lo scafo convesso di punti 2D, dove posso aggiungere e cancellare punti.

L'approccio ingenuo è chiaramente O(N); ogni volta che uno dei punti N viene aggiunto/eliminato, ricalcolo lo scafo convesso da zero. Tuttavia, non posso permettermi il tempo lineare, quindi sto cercando un algoritmo sublineare. Finora, ho trovato un mucchio di carta che descrive un algoritmo sofisticato con limiti di tempo pazzeschi che richiederebbero anni per essere implementato. Anche il più vecchio algoritmo efficiente, dovuto a Overmars e Leeuween, che è O(log^2 N), sembra troppo complicato. (Come al solito, la maggior parte degli algoritmi descritti in tali articoli hanno tonnellate di dipendenze in termini di strutture/algoritmi da altri documenti di riferimento)

Sto cercando qualcosa di più semplice, non necessariamente nuovo, che esegue meglio di lineare nel caso peggiore (ad es. O(sqrt N)). Infine, non mi importa se il tempo è ammortizzato. Qualche idea?

(da semplice, in primo luogo dire qualcosa che non richiede più di qualche centinaio di righe di codice.)

Answer 1

Penso che ciò che cercate non esiste. L'algoritmo Overmars e vanLeeuwen non è così complicato, e sembra in un certo senso necessario. Innanzitutto, cambia il problema mantenendo separatamente lo scafo superiore e lo scafo inferiore. Secondo, costruisci ognuno per divisione e conquista, ma mantieni le strutture intermedie dell'albero, in modo da conoscere gli scafi degli insiemi 1/2, i set 1/4, ecc. Ora, quando cancelli un punto, ricalcolare solo i suoi antenati nell'albero. Quando aggiungi un punto, scopri a quale foglia si unisce, e di nuovo ricalcolato verso l'alto alla radice.

Penso che se ignori i dettagli nel loro articolo e segui semplicemente questo schizzo di alto livello e attui tutti i passaggi nel modo più insensato, non sarà complicato e sarà subliminale.

---

M. H. Overmars e J. van Leeuwen. Manutenzione delle configurazioni nel piano. J. Comput. Syst. Sci., 23: 166-204, 1981.

Answer 2

Suppongo che ci siano N punti dati in totale e lo scafo complesso sia definito da punti M.

Dovrebbe essere molto più facile (e meno costoso) mantenere uno Scafo Convesso piuttosto che costruirlo in primo luogo.

Rimuovere un punto dati esistente

1/ If the data point in not one of the M points defining the convex hull then it won’t affect the hull so just remove it. 

2/ If it is part of the convex hull then you need to adjust the hull – more on that below in point 4 

Aggiunta di un nuovo punto di dati.

3/ If a data point is inside the complex hull then it will not affect the hull. 

Ecco un modo semplice per testare questo fuori dalla parte superiore della mia testa. Crea una triangolazione dell'interno dello scafo. Uno scafo complesso definito usando i punti M può essere triangolato in triangoli M-2. Quindi prova se il punto si trova in uno dei triangoli.

4/ if a data point is outside the hull then it will become part of the hull. However, it is only affecting a local area of the hull and it is straightforward to find the new hull in a few steps. If you have already build the hull then it should be clear to you how to adjust a local part of it. 

Io non vedo come tutto questo manutenzione può essere O (N)

Answer 3

Rispetto al Prof.O'Rourke, che sa molto più di quanto possa fare sulla geometria computazionale, non vedo come un'implementazione "senza cervello" di OvL (cioè, che manca di riequilibrio) potrebbe essere sublimata nel nel caso peggiore.

Fortunatamente, abbiamo fatto alcuni progressi nelle strutture dati dal 1981. In particolare, poiché una garanzia ammortizzata è sufficiente, gli alberi di diffusione (1985) sono appropriati per la memorizzazione sia degli scafi convessi che dell'albero di fusione. Austern et al. (2003) ha proposto un buon modo per separare la manutenzione dei campi aggiuntivi che saranno richiesti dalle complesse operazioni di bilanciamento, in modo da poter scrivere le parti più complicate una volta.

La principale difficoltà nell'implementazione degli alberi di diffusione è l'operazione di splay, e anche quella è molto più semplice di, per esempio, l'inserimento in un albero rosso-nero. Una volta che lo splay funziona, gli splay tree sono easy da dividere e unire. Per dividere, splay il nodo che vuoi dividere dopo e tagliare il suo bambino giusto. Per partecipare, splay il nodo più a destra del primo albero e fai il secondo albero il figlio giusto di quel nodo.