Zanimljiv zadačić!!!
I ja sam pokušavao da razmatram sličan problem... mada sam na tome i stao na nivou razmišljanja o tome hehe
Da li su i Pi poligoni nekonveksni?
Da li se smiju preklapati tj da li je Pn presek Pm = 0 za svako p i m, pod uslovom za n različito od m?

Jesu nekonveksni i ne smiju se preklapati (tako bitno a zaboravio sam napomenuti :P) Stavise problem je jos slozeniji ali hocemo da pocenmo odnekud pa cemo onda ici u detalje (na poligonima mogu biti rupe, pa onda neki dijelovi malih poligona ne smiju lezati na nekim dijelovima onog velikog poligona itd. ali ovo za kasnije :D)

Ja razmisljam o tome da bi mozda najbolje bilo gledati tako da se krene od jedne strane poligona i da se ona popunjava sa ovim manjim poligonima iduci ka suprotnoj strani.

Gleda se koji je cosak P1 najlevlji.
Medju manjim poligonima se trazi onaj ciji je bilo koji ugao na cosku sto manji i proverava se da li taj postavljeni (postavljen je tako sto je zarotiran da njegov ugao na cosku bude u uglu P1) poligon u potpunosti nalazi u P1 a da je postavljen uz ivicu.
U slucaju da ima vise odgovarajucih poligona prednost ce imati manji poligoni, ili ako taj jedan ima vise odgovarajucih uglova moze se napraviti grananje, pa se za svaku mogucnost ponavlja ceo postupak, stim sto P1, sada izgleda kao da mu je deo koji taj poligon zauzima oduzet. Tu bi nastupilo stvaranje hierarhije.
U slucaju da ni jedan poligon ne odgovara cosku gleda se za sledeci najlevlji ugao.
Postupak se ponavlja sve dok P1 ne postane previse mali, tj da nema vise odgovarajucih poligona koji mogu da se smeste u njega ili da ponestane poligona. Posto bi verovatno bilo vise grananja logicno je da se uzima ono gde je ostao najmanji broj neiskoriscenih poligona.

Problem bi mozda mogao da se javi zato sto se sve vreme gleda samo leva strana, mozda bi bilo bolje kada bi se kreatalo sa svih ivica. U svakom slucaju moguce je da traba da se postavi neka hierarhija na osnovu koje moze lakse da se zakljuci gde sta treba da ide.

Hierarhija bi mogla da bude u smislu da se gleda da li je neki od manjih poligona zakomplikovao ovaj veci ili ga je uprostio i na osnovu toga se manjem poligonu dodaje odredjeni broj bodova. Polgon je uproscen u slucaju da je najlevlji ugao sto veci, i da je oduzimanjem tog poligona redukovao ili sto je moguce manje povecao broj stranica. Recimo, za smanjenje broja stranica P1 dobijalo bi se najvise bodova i tako dalje...

Nemam iskustva u vestackoj inteligenciji, ali mislim da bi od ovako necega moglo da se podje :)