Static and kinetic geometric spanners with applications
Static and kinetic geometric spanners with applications
复制标题
静态和动态几何扳手及其应用
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
L. Guibas
中科院分区：
文献类型：
--
作者：
M. Karavelas;L. Guibas
众所周知，Delaunay三角剖分是其顶点的一个图。在本文中，我们证明了任何有界的纵横比三角剖分在二维和三维是一个图的顶点以及。我们扩展的概念，与障碍物的环境中，约束Delaunay三角剖分和有界的纵横比符合三角是speries相对于相应的可见性图。我们还展示了如何动态化约束Delaunay三角剖分。使用这种随时间变化的三角剖分，我们描述了如何保持一组移动点在无约束和约束的环境中的近邻集。在许多邻近代理交互的虚拟环境中，需要这种最近邻维护。最后，我们展示了如何使用约束Delaunay三角剖分，以保持相对凸船体的一组点内移动一个简单的多边形。
It is well known that the Delaunay Triangulation is a spanner graph of its vertices. In this paper we show that any bounded aspect ratio triangulation in two and three dimensions is a spanner graph of its vertices as well. We extend the notion of spanner graphs to environments with obstacles and show that both the Constrained Delaunay Triangulation and bounded aspect ratio conforming triangulations are spanners with respect to the corresponding visibility graph. We also show how to kinetize the Constrained Delaunay Triangulation. Using such time-varying triangulations we describe how to maintain sets of near neighbors for a set of moving points in both unconstrained and constrained environments. Such nearest neighbor maintenance is needed in many virtual environments where nearby agents interact. Finally, we show how to use the Constrained Delaunay Triangulation in order to maintain the relative convex hull of a set of points moving inside a simple polygon.