ON THE SHAPE OF A SET OF POINTS IN THE PLANE
ON THE SHAPE OF A SET OF POINTS IN THE PLANE
复制标题
DOI：
10.1109/tit.1983.1056714
复制
发表时间：
1983-01-01
影响因子：
2.5
通讯作者：
SEIDEL, R
中科院分区：
文献类型：
--
作者：
EDELSBRUNNER, H;KIRKPATRICK, DG;SEIDEL, R
介绍并分析了平面上有限点集的凸包的推广。这种概括导致了一系列直线图“形状”，它们似乎捕捉了点集“精细形状”和“粗略形状”的直观概念。结果表明，a 形是最近点或最远点 Delaunay 三角剖分的子图。依靠这一结果，开发了构造形状的最佳算法。
A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, "-shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimalalgorithm that constructs-shapes is developed.