ผลต่างระหว่างรุ่นของ "โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม"

ไม่มีคำอธิบายอย่างย่อ
ป้ายระบุ: ผู้ใช้ใหม่เพิ่มลิงก์ไปยังเว็บอื่น
ต่อมาในปี 1998 อัลกอริทึมที่ใช้เวลาเฉลี่ยเป็น O(n) ก็ได้ถูกค้นพบและตีพิมพ์โดย [[Alexey V. Skvortsov]] และ [[Yuri L. Kostyuk]] โดยอัลกอริทึมนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม <br/> <br />
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น Ω(n log n)
 
อ้างอิง=
* {{Citation|author = [[Mark de Berg]], [[Marc van Kreveld]], [[Mark Overmars]], and [[Otfried Schwarzkopf]] | year = 2000 | title = Computational Geometry | publisher = [[Springer-Verlag]] | edition = 2nd revised | isbn = 3-540-65620-0}} Chapter 3: Polygon Triangulation: pp.45–61.
* {{Citation |last1=Fournier |first1=A. |author1-link=Alain Fournier |last2=Montuno |first2=D. Y. |author2-link= |title=Triangulating simple polygons and equivalent problems |journal=[[ACM Transactions on Graphics]] |volume=3 |issue=2 | year=1984 <!--|month=April--> |pages=153–174 |issn=0730-0301 |doi=10.1145/357337.357341}}
* Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons," ''Pattern Recognition Letters'', '''2''' (March):155–158.
* Meisters, G. H., "Polygons have ears." American Mathematical Monthly 82 (1975). 648–651
* ElGindy, H., Everett, H., and Toussaint, G. T., (1993) "Slicing an ear using prune-and-search," ''Pattern Recognition Letters'', '''14''', (9):719–722.
* {{Citation |last=Seidel|first=Raimund |author-link= Raimund Seidel| title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons |journal=Computational Geometry: Theory and Applications |volume=1 |year=1991 |pages=51–64}}
* {{Citation |last=Chazelle |first=Bernard |author-link=Bernard Chazelle | title=Triangulating a Simple Polygon in Linear Time |journal=Discrete &amp; Computational Geometry |volume=6 |year=1991|pages=485–524 |issn=0179-5376 |doi=10.1007/BF02574703}}
* {{Citation | author = Skvortsov, Alexey V., Kostyuk, Yuri L. | title = Efficient algorithms for Delaunay triangulation | publisher = Tomsk State University | journal = Geoinformatics. Theory and practice | volume = 1 | year = 1998 | pages = 22–47 | url = http://www.inf.tsu.ru/Library/Publications/1999/Skvortsov_1999_1.pdf}} {{ru icon}}
* {{Citation |last1=Amato |first1=Nancy M. |last2=Goodrich |first2=Michael T. |author2-link=Michael T. Goodrich|last3=Ramos |first3=Edgar A. |title=A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time |journal=Discrete &amp; Computational Geometry |volume=26 |year=2001 <!--|month=May--> |pages=245–265 |issn=0179-5376 |doi=10.1007/s00454-001-0027-x |url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185 |issue=2}}
* http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html
* http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.html
* http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
23

การแก้ไข