Efficient Generation of Plane Triangulations without Repetitions
Efficient Generation of Plane Triangulations without Repetitions
复制标题
高效生成平面三角剖分，无需重复
DOI：
10.1007/3-540-48224-5_36
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Shin
中科院分区：
文献类型：
--
作者：
Zhangjian Li;Shin
“基于”平面三角剖分是在外表面有一个指定边的平面三角剖分。在本文中，我们给出了一种简单的算法来生成所有基于双连通的平面三角形。该算法使用o (n)空间，每个三角剖分在o(1)时间内生成这样的三角剖分，没有重复。该算法输出的不是整个三角剖分，而是与之前的三角剖分的差异。通过修改算法，我们可以生成所有基于双连通的平面三角剖分，每个三角剖分的时间为inO(1)，且没有重复，而之前的最佳算法每次三角剖分生成这种三角剖分的时间为inO（n2）。此外，我们可以在没有重复的情况下生成所有具有精确顶点的双连通（非基于）平面三角形，每个三角剖分的时间为inO(r2n)，并且所有具有精确顶点的最大平面图每个图的时间为inO（n3）。
A “based” plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at mostnvertices. The algorithm usesO(n) space and generates such triangulations inO(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulation having exactlynvertices including exactlyrvertices on the outer face inO(1) time per triangulation without duplications, while the previous best algorithm generates such triangulations inO(n2) time per triangulation. Also we can generate without duplications all biconnected (non-based) plane triangulations having exactlynvertices including exactlyrvertices on the outer face inO(r2n) time per triangulation, and all maximal planar graphs having exactlynvertices inO(n3) time per graph.