论文标题
pslg的非抗突
Nonobtuse triangulations of PSLGs
论文作者
论文摘要
我们表明，任何具有$ n $顶点的平面直线图（PSLG）都有$ O（n^{2.5}）$ o（n^{2.5}）$ nonobtuse triangles（所有角度$ \ leq 90^\ circ $）的三角剖分，回答了是否存在任何多项式边界的问题。非观察三角剖分是Delaunay，因此该结果还改善了Eldesbrunner和TAN的前面$ O（n^3）$，用于符合PSLG的Delaunay三角剖分。在PSLG是简单多边形的三角剖分的特殊情况下，我们将证明只需要$ O（n^2）$三角形，改善了$ O（n^4）$ bound of Bern and Eppstein。我们还表明，对于任何$ε> 0 $，每个PSLG都有一个与$ O（n^2/ε^2）$元素的三角剖分，并且所有角度都在上面的所有角度限制为$ 90^\ Circ +ε$。当$ε=3π/8 = 67.5^\ circ $和tan时，这改善了S. Mitchell的结果。
We show that any planar straight line graph (PSLG) with $n$ vertices has a conforming triangulation by $O(n^{2.5})$ nonobtuse triangles (all angles $\leq 90^\circ$), answering the question of whether any polynomial bound exists. A nonobtuse triangulation is Delaunay, so this result also improves a previous $O(n^3)$ bound of Eldesbrunner and Tan for conforming Delaunay triangulations of PSLGs. In the special case that the PSLG is the triangulation of a simple polygon, we will show that only $O(n^2)$ triangles are needed, improving an $O(n^4)$ bound of Bern and Eppstein. We also show that for any $ε>0$, every PSLG has a conforming triangulation with $O(n^2/ε^2)$ elements and with all angles bounded above by $90^\circ + ε$. This improves a result of S. Mitchell when $ε= 3 π/8 = 67.5^\circ $ and Tan when $ε= 7π/30 =42^\circ$.
