Comincio con una lista di tetraedri adiacenti, dove ci sono sigilli stretti l'uno all'altro lungo le facce di due tetraedri che sono adiacenti. Anche i vertici appartenenti a queste facce per entrambi i tetraedri sono coincidenti. Ci sono alcune facce che sono esposte. Posso usare queste informazioni per creare un grafico di adiacenza, in cui ogni nodo nel grafico rappresenta un tetraedro e ha al massimo 4 vicini diretti. Due nodi nel grafico sono adiacenti se i tetraedri che rappresentano sono adiacenti lungo una faccia.
Il mio problema ora è di minimizzare il numero di gruppi disgiunti di vertici nel grafico in modo tale che ogni sottogramma non sia disconnesso. Devo anche soddisfare i criteri secondo cui per tutti i sotto-grafici, la struttura 3D cumulativa formata dal tetraedro rappresentato dai nodi nel sottogramma è convessa. Cioè, dopo la rimozione delle facce non esposte, tutti i vertici della struttura rimanente cadono su o su un lato del piano di ciascuna faccia esposta.
Mi interessa un algoritmo con complessità molto inferiore ai numeri di Bell perché potrei aver bisogno di eseguirlo su set di dati di grandi dimensioni.
Questo è l'equivalente 2D del problema che è molto più facile da visualizzare:
Esistono due soluzioni ottimali, ciascuna con 2 sottogruppi. Il primo è [{1,2,3,4,5,6,7,8,9,10,11,12}, {13}], e il secondo è [{1,2,3,4,5 , 6,7,8,9,10,11}, {12,13}].