关于平面点集三角剖分的两类子集(英文)

Two Subsets an the Triangulation of a Planar Point Set

英文关键词:triangulation, stable line segment, chain decomposition, algorithm, computational geometry.

中文摘要:

      给定欧氏平面上的一个点集合Ｓ，我们给出两类端点在Ｓ中的线段集合，第一类线段集合是Ｓ的任一三角剖分的子集，第二类线段集合是Ｓ的任一最小权三解剖分的子集，这两类子集是不相交的，这两类子集合的计算要用Ｏ(n³)时间和Ｏ（ｎ）空间．

英文摘要:

      Given a finite set S of points in the Euclidean plane, we propose two kinds of line segment sets with endpoints in S. the first kind of line segment set is a subset of any triangulation of S, the second kind of line segment set is a subset of any minimum weight triangulation of S, and the two sets are disjoint. The computation of the two sets takes O(n³) time and O(n) space.