Sokszög felosztása

A sokszög felosztás primitív elemek (például négyzetek) halmaza, amelyek nem fedik át egymást, és amelyek uniója megegyezik egy sokszöggel. A poligon partíciós probléma egy bizonyos értelemben minimális partíció megtalálásának problémája, például a legkisebb elemszámú partíció vagy a legkisebb oldalhosszúságú partíció.

A sokszög particionálás a számítási geometria egyik fontos problémaosztálya . A sokszög típusától és a megengedett elemek típusától függően számos különböző poligon particionálási probléma merül fel.

A poligonfelbontás kifejezést gyakran használják a lefedés és a particionálás általános kifejezéseként [1] .

Alkalmazások

A sokszögbontást számos területen használják [1] :

Sokszög felosztása háromszögekre

A legtöbbet tanulmányozott sokszög particionálási probléma a legkisebb számú háromszögre történő particionálás ( háromszögelés ). Egy csúcsú lyukak nélküli sokszög esetén a háromszögelés időben kiszámítható . Van egy alsó korlátja a lyukakkal rendelkező sokszögnek .

Ehhez kapcsolódó probléma a legkisebb oldalösszegű háromszögelés ( minimális súlyú háromszögelés ).

Sokszög felosztása pszeudoháromszögekre

A feladatnak ugyanaz a két változata vethető fel arra az esetre, amikor háromszögek helyett pszeudo -háromszögeket használunk – olyan sokszögeket, amelyeknek a háromszögekhez hasonlóan pontosan három konvex csúcsuk van. Változatok: felosztás kisebb számú pszeudo-háromszögre, és a legkisebb teljes oldalhosszúságú pszeudoháromszögekre.

Sokszög felosztása téglalapokra

A poligonfelosztási probléma speciális esete akkor fordul elő, ha a felosztandó sokszög egy merőleges sokszög . Ebben az esetben a felosztás legfontosabb összetevője a téglalap [1] .

A téglalap alakú válaszfalakat gyakran használják. A VLSI tervezésekor a maszkot egyszerű formákra kell bontani, amelyek elérhetők a litográfiai generátor listájában. Hasonló bomlási probléma merül fel a DNS microarray-ek fejlesztése során . A téglalap alakú partíciók leegyszerűsíthetik a képfeldolgozás konvolúciós műveleteit, és bittérképek tömörítésére is használhatók . A mátrix felosztásának szorosan kapcsolódó problémája a sugárterápia tervezésére vonatkozik . A téglalap alakú particionálást a robot önszerelődési sorozatának megtervezésére használják [2] [3] .

Számos polinomiális futási idejű algoritmus ismert erre a problémára, lásd Mark Keil [4] és Eppstein [5] áttekintését.

Egy téglalap alakú sokszögnek a legkevesebb négyzetre történő particionálása (szemben a tetszőleges téglalapokkal) NP-nehéz probléma [6] .

Sokszög felbontása trapézokra

A VLSI fejlesztése során gyakran szükséges egy sokszögű régiót minimális számú trapézre osztani , két vízszintes alappal. A vízszintes alappal rendelkező háromszög is trapéznak számít, amelynek egyik alapja degenerált. Az oldalsó lyukak nélküli sokszögeknél a legkisebb ilyen partíció időben megtalálható [7] .

Ha nem szükséges a trapézok számának minimálisnak lennie, a partíció a sokszög háromszögelési algoritmus [8] melléktermékeként időben megtalálható .

Ha a sokszögben lyukak vannak, a feladat NP-teljessé válik, de időben találhatunk egy 3-as közelítést [7] .

Sokszög particionálása konvex négyszögekre

Felveheti a sokszög konvex négyszögekre történő particionálásának problémáját .

A négyszögprobléma lényeges jellemzője, hogy a Steiner-pontok megengedettek-e vagy sem , pl. szabad-e olyan pontokat hozzáadni, amelyek nem sokszög csúcsok. Ha a Steiner-pontokat engedélyezzük, akkor kisebb partíciót kaphatunk, de sokkal nehezebb garantálni, hogy az algoritmusok által talált partíciók minimális méretűek legyenek.

A lyukak nélküli sokszögeknél léteznek lineáris idő algoritmusok a Steiner-pontokkal történő négyszögesítéshez, de nincs garancia arra, hogy a talált megoldás a legkisebb lesz [9] [10] .

Sokszög felbontása m - szögekre

Az előző probléma általánosítása az a probléma, hogy egy sokszöget pontosan m , de legfeljebb m oldalú sokszögekre osztunk fel. A cél az oldalak teljes hosszának minimalizálása. A feladat megoldható polinomiális időben n -ben és m -ben [ 11] [12] .

Általánosabb típusú ábra

Általánosabb alakzatokat is feltártak, köztük tetszőleges konvex sokszögeket , spirálokat , csillag sokszögeket és monoton sokszögeket . Lásd Mark Cale cikkét [1] az áttekintésért .

Lásd még

Jegyzetek

  1. ↑ 1 2 3 4 Mark Keil, 2000 , p. 491.
  2. ↑ Eppstein, 2010 , p. egy.
  3. ↑ Li, Zhang, 2005 , p. 3213-3218.
  4. ↑ Mark Keil, 2000 , p. 10–13.
  5. ↑ Eppstein, 2010 , p. 3–5.
  6. ↑ Realz Slaw .
  7. ↑ 1 2 Asano, Asano, Imai, 1986 , p. 290.
  8. ↑ Chazelle, 2007 , p. 485.
  9. ↑ Everett et al., 1992 , p. 77–83.
  10. ↑ Ramaswami, Ramos, Toussaint, 1998 , p. 257.
  11. ↑ Lingas, Levcopoulos, Sack, 1987 , p. 474.
  12. ↑ Levcopoulos, Lingas, Sack, 1989 , p. 181.

Irodalom