Algoritmo per trovare il minor numero di rettangoli per coprire una serie di rettangoli senza sovrapposizione

Question

Ho una serie di rettangoli e vorrei "ridurre" il set in modo da avere il minor numero di rettangoli per descrivere la stessa area del set originale. Se possibile, vorrei che fosse anche veloce, ma sono più preoccupato di ottenere il numero di rettangoli il più basso possibile. Ora ho un approccio che funziona per la maggior parte del tempo.

Attualmente, inizio più rettangolo in alto a sinistra e vedo se riesco a espanderlo a destra e giù mantenendolo un rettangolo. Lo faccio fino a quando non può più espandersi, rimuovere e dividere tutti i rettangoli intersecanti e aggiungere il rettangolo ampliato nell'elenco. Quindi ricomincio il processo con il prossimo rettangolo in alto a sinistra e così via. Ma in alcuni casi, non funziona. Per esempio:

Con questo set di tre rettangoli, la soluzione corretta finirebbe con due rettangoli, come questo:

Tuttavia, in questo caso, il mio algoritmo inizia elaborando il rettangolo blu. Questo si espande verso il basso e divide il rettangolo giallo (correttamente). Ma poi quando il resto del rettangolo giallo viene elaborato, invece di espandersi verso il basso, si espande prima e riprende la parte che era stata precedentemente divisa. Quindi l'ultimo rettangolo viene elaborato e non può espandersi a destra o in basso, quindi viene lasciato l'insieme originale di rettangoli. Potrei modificare l'algoritmo per espandermi prima e poi a destra. Ciò risolverebbe questo caso, ma causerebbe lo stesso problema in uno scenario simile che è stato capovolto.

Modificare: Solo per chiarire, l'insieme originale di rettangoli non si sovrappone e non deve essere collegato. E se un sottoinsieme di rettangoli è collegato, il poligono che li copre completamente può avere fori.