Polygontrianguleringsproblem

Problemet med att triangulera en polygon  är ett klassiskt problem med kombinatorisk och beräkningsgeometri , som består i att hitta en triangulering av en polygon utan ytterligare hörn.

Beviset för existensen av en sådan triangulering är inte svårt. Dessutom har detta problem alltid en lösning för polygoner med hål, det vill säga områden av planet som begränsas av flera slutna brutna linjer.

Formulering

Problemet är att hitta den optimala algoritmen för att triangulera en n - gon utan ytterligare hörn.

Detta problem kan lösas i linjär tid , det vill säga problemet har komplexitet .

Historik

Länge var frågan öppen om det är möjligt att hitta trianguleringen av en n-gon i tid mindre än . [1] Van Wyck (1988) upptäckte sedan en algoritm som kräver tid , [2] senare förenklad av Kirkpatrick och Clave. [3] Detta följdes av flera algoritmer med komplexitet (där är den itererade logaritmen av ) som i praktiken inte går att skilja från linjär tid . [4] [5] [6]

1991 bevisade Bernard Chazelle att vilken enkel polygon som helst kan trianguleras i linjär tid, även om algoritmen han föreslog visade sig vara mycket komplicerad. [7] En enklare probabilistisk algoritm med linjär förväntad tid är också känd. [8] [9]

Algoritmer

Öronklippning

Den dubbla trianguleringsgrafen utan ytterligare hörn av en enkel polygon är alltid ett träd . Det följer särskilt att varje enkel n -gon med n > 3 har minst två öron , det vill säga två trianglar, varav två sidor är sidor av polygonen, och den tredje är helt inuti den. [tio]

Ett sätt att triangulera är att hitta ett sådant öra och skära av det från polygonen. Därefter upprepas samma operation på den återstående polygonen tills en triangel återstår.

Denna metod fungerar bara för polygoner utan hål. Det är enkelt att implementera men långsammare än vissa andra algoritmer. En implementering som håller separata listor över konvexa och konkava hörn körs i tid .

En effektiv algoritm för att skära av öron föreslogs av Hossam El-Gindi, Hazel Everett och Godfried Toussaint. [elva]

Genom monotona polygoner

En polygon kallas monoton om dess gränspolygon har högst två skärningspunkter med en linje vinkelrät mot den givna.

En monoton polygon kan trianguleras i linjär tid med algoritmen för A. Fournier och D. Yu. Montuno [12] eller algoritmen från Godfried Toussaint. [13]

En godtycklig polygon kan delas upp i monotona. En enkel polygontrianguleringsalgoritm baserad på denna idé körs i tid .

Variationer och generaliseringar

Se även

Anteckningar

  1. ↑ Mark de Berg, Marc van Kreveld, Mark Overmars och Otfried Schwarzkopf (2000), Computational Geometry (2nd revided ed.), Springer-Verlag , ISBN 3-540-65620-0 
  2. ↑ Tarjan, Robert E. & Van Wyk, Christopher J. (1988), An O( n log log n )-time algorithm for triangulating a simple polygon , SIAM Journal on Computing vol. 17(1): 143–178 , DOI 10.1137/0217010  .
  3. ↑ Kirkpatrick, David G.; Klawe, Maria M. & Tarjan, Robert E. (1992), Polygontriangulering i O( n log log n ) tid med enkla datastrukturer , Discrete and Computational Geometry vol. 7 (4): 329–346 , DOI 10.1007/BF02187846  .
  4. ↑ Clarkson, Kenneth L.; Tarjan, Robert & van Wyk, Christopher J. (1989), En snabb Las Vegas-algoritm för triangulering av en enkel polygon , Discrete and Computational Geometry Vol. 4: 423–432 , DOI 10.1007/BF02187741  .
  5. ↑ Seidel, Raimund (1991), A Simple and Fast Incremental Randomized Algorithm for Computing trapezoidal decompositions and for triangulating polygons , Computational Geometry: Theory and Applications Vol. 
  6. ↑ Clarkson, Kenneth L.; Cole, Richard & Tarjan, Robert E. (1992), Randomized parallel algorithms for trapezoidal diagrams , International Journal of Computational Geometry & Applications vol 2 (2): 117–133 , DOI 10.1142/S0218195992000081  .
  7. ↑ Chazelle, Bernard (1991), Triangulating a Simple Polygon in Linear Time , Discrete & Computational Geometry vol. 6: 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 vol. 26 (2): 245–265, ISSN 0179-5376 , doi : 10.1007 /s00454-001-0027-x , < http://parasol.tamu.edu/publications/abstract.php?pub_id=185 > Arkiverad 23 juli 2018 på Wayback Machine 
  9. ↑ Li, Fajie & Klette, Reinhard (2011), Euclidean Shortest Paths , Springer , ISBN 978-1-4471-2255-5 , DOI 10.1007/978-1-4471-2256-2  .
  10. ↑ Meisters, GH, "Polygoner har öron."
  11. ↑ ElGindy, H.; Everett, H.; Toussaint, GT Skiva ett öra med beskära-och-  sök //  Mönsterigenkänningsbokstäver : journal. - 1993. - Vol. 14 , nr. 9 . - s. 719-722 . - doi : 10.1016/0167-8655(93)90141-y .
  12. ↑ Fournier, A. & Montuno, DY (1984), Triangulating simple polygons and equivalent problems , ACM Transactions on Graphics vol. 3 (2): 153–174, ISSN 0730-0301 , DOI 10.1145/357341.357 
  13. ↑ Toussaint, Godfried T. (1984), "En ny linjär algoritm för triangulering av monotona polygoner," Pattern Recognition Letters , 2 (mars):155-158.
  14. ↑ Pickover, Clifford A., The Math Book , Sterling, 2009: s. 184.

Länkar