The Zigzag Path of a Pseudo-Triangulation
The Zigzag Path of a Pseudo-Triangulation
复制标题
伪三角剖分的锯齿形路径
DOI：
10.1007/978-3-540-45078-8_33
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
I. Streinu
中科院分区：
文献类型：
--
作者：
O. Aichholzer;G. Rote;B. Speckmann;I. Streinu
我们定义了伪三角剖分的曲折路径，这是一个推广点集的三角剖分路径的概念。伪三角测量之字形路径允许我们使用分治类型的方法来进行适当的（即，可分解的）伪三角剖分问题。为此，我们提供了一个算法，枚举所有的伪三角形之字形路径（一个给定的点集相对于一个给定的线的所有伪三角形）在O（n2）的时间每路径和O（n2）的空间，其中是点的数量。我们说明了我们的计划，其中包括一个新的算法来计算一个点集的伪三角剖分的数量的应用。
We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudo-triangulation zigzag path allows us to use divide-and-conquer type of approaches for suitable (i.e., decomposable) problems on pseudo-triangulations. For this we provide an algorithm that enumerates all pseudo-triangulation zigzag paths (of all pseudo-triangulations of a given point set with respect to a given line) inO(n2) time per path andO(n2) space, wherenis the number of points. We illustrate applications of our scheme which include a novel algorithm to count the number of pseudo-triangulations of a point set.