sfera o rettangolo vuoto più grande

Question

In N (~ 500) dimensioni, desidero trovare la sfera o il rettangolo più grande in modo che la sfera/il rettangolo non contenga punti già esistenti. L'intera serie di punti è limitata in una casella rettangolare allineata all'asse (limiti inferiore e superiore sui valori).

Esiste un metodo/codice temporale polinomico noto che è possibile utilizzare per risolvere il problema?

I due algoritmi noti: i) il rettangolo vuoto più grande all'interno di un rettangolo (http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf) e, ii) trovare il cerchio vuoto più grande all'interno dei vincoli di posizione (http://www.cs.dartmouth.edu/reports/TR86-130.pdf) non funzionano.

Sebbene la complessità degli algoritmi di cui sopra sia N log N o N^2 log N, dove N è il numero di punti già esistenti, la complessità è anche una funzione lineare del numero di vertici dello scafo convesso o del limite poligono. Un rettangolo in 500 dimensioni avrà 2^500 angoli che rende le tecniche di cui sopra non fattibili.

Idealmente, sto cercando un metodo (non deve essere esatto) che può determinare il più grande cerchio/rettangolo in tempo polinomiale in N (numero di punti) e D (la dimensione).

Grazie.

Answer 1

Una possibile soluzione euristica consiste nel limitare il rettangolo grande in modo che sia allineato sull'asse. In questo caso, un rettangolo può essere limitato al massimo da 2 * punti d, in cui ogni punto rappresenta un limite di limitazione o un massimo di una o più dimensioni. Può essere quindi determinato se un punto si trova all'interno di quel rettangolo solo in O (d).

Un metodo euristico per utilizzare questo è per selezionare 2 punti e utilizzare quelli per formare un riquadro di delimitazione iniziale, quindi aggiungere punti in modo casuale. Se il punto si trova all'interno della scatola, rimpicciolisci o dividi la scatola. Se il punto è al di fuori della scatola, prova a ingrandire la scatola. Un singolo passaggio dovrebbe richiedere O (d * N) se la casella viene ristrut- ta anziché divisa.

La qualità può essere leggermente migliorata assicurandosi che nessun punto si trovi all'interno del riquadro di delimitazione formato dai due punti. Potrebbe essere ideale trovare tutte le coppie di punti in modo che nessun punto si trovi all'interno del riquadro di delimitazione, poiché quando vengono convertiti in un grafico, dovrebbero aiutare ad espandere la soluzione in un modo meno casuale. La programmazione dinamica probabilmente porta ad un algoritmo che è migliore di O (d * N^3) forse O (d * N^2) o migliore.