Pētnieciskās problēmas

Taisnstūru izvietojuma normalizēšana

  Plaknē patvaļigi izvietots liels daudzums taisnstūru ar asīm paralēlām malām (t.i. to malas ir vai nu vertikālas, vai horizontālas).
  Izstrādāt algoritmu tāda jauna šo taisnstūru izvietojuma atrašanai, lai
(1) taisnstūri nešķeltos,
(2) taisnstūri joprojām būtu asīm paralēli,
(3) kopējais taisnstūru pārvietojums būtu pēc iespējas mazs.
  Papildus taisnstūru jaunajam izvietojumam var arī pieprasīt, lai taisnstūri atrastos vertikālās un horizontālās rindās.
  Zemāk redzams piemērs ar taisnstūriem pirms un pēc normalizēšanas, bet ne ar iespējami mazāko kopējo taisnstūru pārvietojumu.

  Līdzīgi uzdevumu var formulēt arī citām figūrām, piemēram, riņķiem:


Uz galveno lapu