Ho un insieme di punti spaziali definiti da coordinate (x, y). Voglio trovare il rettangolo di delimitazione di un'area data che massimizza il numero di punti all'interno del rettangolo. Il rettangolo ottenuto dovrebbe avere lati paralleli agli assi di coordinate.
Si prega di suggerire.
Forse (ripeti, forse) prima trova il rettangolo di delimitazione, indipendentemente dall'area, come descritto da "Mandrill" sopra (che apparentemente trascurava il vincolo "area data"). Quindi il tuo "rettangolo dell'area dato" sarà all'interno di quello. Oppure, se quel rettangolo di delimitazione è già la tua area data o meno, allora hai finito. Altrimenti, scegli un angolo e inizia a spostarlo "verso l'interno" in x, perdendo sicuramente un punto, finché non raggiungi un secondo punto. Quindi spostalo "verso l'interno" in y fino a quando non premi di nuovo un secondo punto. In questo modo si riduce il più possibile il rettangolo, mentre si perde solo il punto più esterno rispetto all'angolo selezionato. Salva l'area risultante. Ora riavvia il rettangolo originale e prova ciascuno degli altri tre angoli a turno. Quindi avrai quattro rettangoli, ognuno con un punto perso. Scegli il rettangolo dell'area minima tra questi quattro. E ora ricomincia da quel rettangolo. Ecc, ecc., Fino a quando non si ottiene l'area richiesta.
Ora, questo ti darà sicuramente un "minimo locale". Ma non sono affatto sicuro che ti porterà il "minimo globale".
Ecco un semplice approccio a forza bruta. Sia A l'area data e il numero di punti.
Trova il riquadro di delimitazione di tutti i punti. Se la sua area è inferiore o uguale a A, hai finito (un rettangolo di dimensioni < A può essere sempre banalmente esteso ad un rettangolo di dimensione A).
Genera tutti "(n-1) -subsets" (sottoinsiemi di dimensione n-1) dell'insieme di tutti i punti. Metti alla prova le loro caselle di delimitazione come in 1. Ferma se ne hai trovato uno.
Genera tutti "(n-2) -subsets", verifica i loro riquadri di delimitazione, quindi tutti i n-3-sottoinsiemi e così via. Vedi questo vecchio SO pubblica come generare k- sottoinsiemi in generale.
Attenzione, il tempo di esecuzione peggiore di questo algoritmo potrebbe essere O (2 ^ n). Se questo approccio è ok, o troppo lento per il tuo caso dipende da n, A e dalla distribuzione effettiva dei punti.
Leggi altre domande sui tag algorithms algorithm-analysis