Triangulation邓俊辉清华大学计算机系2026年9月17日星期四上午12时46分
Triangulation 邓俊辉 清华大学计算机系 2026年9月17日星期四上午12时46分
Triangulation of PolygonPolygonExistence:yeswith/withoutholesUniqueness:no usuallySimplepolygons- O(nlogn)Garey etal.,1978- O(nloglogn)R.E.Tarjan&C.J.VanWyk,1988expected-O(nlogn)K.Clarkson,R.E.Tarjan and C.J.VanWyk,1989- O(n)B.Chazelle,1991(bytrapezoidalization)N.M.Amato, etal.,2001 (byrandomization)expected-O(n)Art gallery2国Optimal triangulation-e.g.,minimumink/maximizingtheminimumangle/
Triangulation of Polygons ☞ Polygon – Existence: yes with/without holes – Uniqueness: no usually ☞ Simple polygons – O(nlogn) Garey et al., 1978 – O(nloglogn) R. E. Tarjan & C. J. Van Wyk, 1988 – expected-O(nlog*n)K. Clarkson, R. E. Tarjan and C. J. Van Wyk, 1989 – O(n) B. Chazelle, 1991 (by trapezoidalization) – expected-O(n) N. M. Amato, et al., 2001 (by randomization) ☞ Art gallery ☞ Optimal triangulation – e.g., minimum ink / maximizing the minimum angle /
Triangulation of Point SetProblemGive a set V of n points in the planeconstructamaximal planargraphTV)taking V asthevertexsetExistence!Uniqueness?AlgorithmsBrute-force美Plane-sweep
Triangulation of Point Sets ☞ Problem – Give a set V of n points in the plane l construct a maximal planar graph T(V) taking V as the vertex set – Existence! – Uniqueness? ☞ Algorithms – Brute-force – Plane-sweep –
GreedytriangulationIdeaasimulation oftheKruskal algorithmforMSTOptimaltriangulationnotguaranteedoptimal triangulation=?later
Greedy triangulation ☞ Idea – a simulation of the Kruskal algorithm for MST ☞ Optimal triangulation – not guaranteed – optimal triangulation = ? l later
Greedy TriangulationAlgorithmsCNaive0(n3) / 0(n2)[Gi79]0(n2logn) / 0(n2)[Go89][Li88]O(n2logn) / O(n)[LL92][Wa93]0(n2) / 0(n)-[Lev92][Wa94]O(nlogn) /O(n) (without necessary proofs)- [LK99]O(nlogn) / O(n) (with proof)GSpecialcasesDelaunay Triangulation ---O(n)--> GTEMST ---O(n)-->DT
Greedy Triangulation ☞ Algorithms – Naive O(n3) | O(n2) – [Gi79] O(n2logn) | O(n2) – [Go89][Li88] O(n2logn) | O(n) – [LL92][Wa93] O(n2) | O(n) – [Lev92][Wa94] O(nlogn) | O(n)(without necessary proofs) – [LK99] O(nlogn) | O(n)(with proof) ☞ Special cases – Delaunay Triangulation -O(n)-> GT – EMST -O(n)-> DT