Sokszög háromszögelési probléma

A sokszög háromszögelésének problémája a kombinatorikus és számítási geometria  klasszikus problémája , amely abból áll, hogy egy sokszög háromszögét további csúcsok nélkül kell megtalálni.

Egy ilyen háromszögelés létezésének bizonyítása nem nehéz. Sőt, ennek a feladatnak mindig van megoldása a lyukakat tartalmazó sokszögekre, vagyis a sík több zárt szaggatott vonallal határolt területeire.

Megfogalmazás

A probléma az, hogy megtaláljuk az optimális algoritmust egy n - szög további csúcsok nélküli háromszögeléséhez.

Ez a probléma lineáris időben megoldható , vagyis a probléma összetett .

Történelem

Sokáig nyitott volt a kérdés, hogy meg lehet-e találni egy n-szög háromszögelését a -nál kisebb időben . [1] Van Wyck (1988) ezután felfedezett egy időigényes algoritmust , [2] amelyet később Kirkpatrick és Clave egyszerűsített. [3] Ezt számos bonyolultságú algoritmus követte (ahol az iterált logaritmus ), amelyek a gyakorlatban megkülönböztethetetlenek a lineáris időtől . [4] [5] [6]

1991-ben Bernard Chazelle bebizonyította, hogy bármely egyszerű sokszög háromszögezhető lineáris időben, bár az általa javasolt algoritmus nagyon bonyolultnak bizonyult. [7] Egy egyszerűbb valószínűségi algoritmus is ismert lineáris várható idővel. [8] [9]

Algoritmusok

Fülvágás

Az egyszerű sokszög további csúcsai nélküli kettős háromszögelési gráf mindig egy fa . Ebből különösen az következik, hogy minden egyszerű n -szögnek, amelynek n > 3 van, legalább két füle van, azaz két háromszöge, amelyek mindegyikének két oldala a sokszög oldala, a harmadik pedig teljesen a sokszög belsejében van. [tíz]

A háromszögelés egyik módja, ha megkeresünk egy ilyen fület, és levágjuk a sokszögről. Ezt követően ugyanazt a műveletet ismételjük a fennmaradó sokszögön, amíg egy háromszög marad.

Ez a módszer csak lyuk nélküli sokszögeknél működik. Egyszerűen megvalósítható, de lassabb, mint néhány más algoritmus. A konvex és konkáv csúcsok külön listáját kezelő megvalósítás időben fut .

A fülek levágására szolgáló hatékony algoritmust Hossam El-Gindi, Hazel Everett és Godfried Toussaint javasolta. [tizenegy]

Monoton sokszögeken keresztül

Egy sokszöget monotonnak nevezünk, ha a határpoligonnak legfeljebb két metszéspontja van az adott pontra merőleges egyenessel.

Egy monoton sokszög háromszögezhető lineáris időben A. Fournier és D. Yu. Montuno [12] algoritmusával vagy Godfried Toussaint algoritmusával. [13]

Egy tetszőleges sokszög monoton poligonokra osztható. Az ezen az elgondoláson alapuló egyszerű sokszög háromszögelési algoritmus időben fut .

Változatok és általánosítások

Lásd még

Jegyzetek

  1. ↑ Mark de Berg, Marc van Kreveld, Mark Overmars és Otfried Schwarzkopf (2000), Computational Geometry (2. felülvizsgált kiadás), Springer-Verlag , ISBN 3-540-65620-0 
  2. ↑ Tarjan, Robert E. & Van Wyk, Christopher J. (1988), An O( n log log n )-time algoritmus egy egyszerű sokszög háromszögezésére , SIAM Journal on Computing 17(1): 143–178 , DOI 10.1137/0217010  .
  3. ↑ Kirkpatrick, David G.; Klawe, Maria M. & Tarjan, Robert E. (1992), Polygon triangulation in O( n log log n ) time with simple data structures , Discrete and Computational Geometry vol. 7 (4): 329–346 , DOI 10.1007/BF02187846  .
  4. ↑ Clarkson, Kenneth L.; Tarjan, Robert & van Wyk, Christopher J. (1989), Egy gyors Las Vegas-i algoritmus egy egyszerű sokszög háromszögeléséhez , Discrete and Computational Geometry 4. kötet: 423–432 , DOI 10.1007/BF02187741  .
  5. ↑ Seidel, Raimund (1991), Egy egyszerű és gyors növekményes véletlenszerű algoritmus trapézfelbontások kiszámításához és sokszögek háromszögeléséhez , Számítási geometria: Elmélet és alkalmazások 1. kötet: 51–64 , DOI 10.1016-7-7401(7) 
  6. ↑ Clarkson, Kenneth L.; Cole, Richard & Tarjan, Robert E. (1992), Véletlenszerű párhuzamos algoritmusok trapézdiagramokhoz , International Journal of Computational Geometry & Applications 2. kötet (2): 117–133 , DOI 10.1142/S0218195992000081  .
  7. ↑ Chazelle, Bernard (1991), Triangulating a Simple Polygon in Linear Time , Discrete & Computational Geometry 6. kötet: 485–524, ISSN 0179-5376 , DOI 10.1007/BF02574703 
  8. ↑ Amato, Nancy M.; Goodrich, Michael T. & Ramos, Edgar A. (2001), A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time , Discrete & Computational Geometry 26. kötet (2): 245–265, ISSN 0179-5376 , doi : 10.1007 /s00454-001-0027-x , < http://parasol.tamu.edu/publications/abstract.php?pub_id=185 > Archivált : 2018. július 23. a Wayback Machine -nél 
  9. ↑ Li, Fajie és Klette, Reinhard (2011), Euclidean Shortest Paths , Springer , ISBN 978-1-4471-2255-5 , DOI 10.1007/978-1-4471-2256-2  .
  10. ↑ Meisters, GH, "A sokszögeknek fülük van."
  11. ↑ ElGindy, H.; Everett, H.; Toussaint, GT Fül felvágása aszalt szilvával és kereséssel  //  Pattern Recognition Letters : folyóirat. - 1993. - 1. évf. 14 , sz. 9 . - P. 719-722 . - doi : 10.1016/0167-8655(93)90141-y .
  12. ↑ Fournier, A. & Montuno, DY (1984), Egyszerű sokszögek háromszögelése és ekvivalens problémák , ACM Transactions on Graphics 3. kötet (2): 153–174, ISSN 0730-0301 , DOI 10.1145/35573347. 
  13. ↑ Toussaint, Godfried T. (1984), "Új lineáris algoritmus a monoton poligonok háromszögeléséhez", Pattern Recognition Letters , 2. (március):155-158.
  14. ↑ Pickover, Clifford A., The Math Book , Sterling, 2009: p. 184.

Linkek