Paper Info
Title
Static and kinetic geometric spanners with applications
Abstract
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.
Year
DOI
Venue
2001
10.5555/365411.365441
SODA
Keywords
Field
DocType
bounded aspect ratio triangulation,time-varying triangulations,corresponding visibility graph,nearest neighbor maintenance,spanner graph,bounded aspect ratio,near neighbor,constrained delaunay triangulation,kinetic geometric spanner,nearby agents interact,delaunay triangulation,covering,aspect ratio,convex hull,virtual environment,manufacturing,np completeness,nearest neighbor,three dimensions,kinetics,approximation algorithms
Discrete mathematics,Combinatorics,Bowyer–Watson algorithm,Minimum-weight triangulation,Beta skeleton,Computer science,Triangulation (social science),Constrained Delaunay triangulation,Polygon triangulation,Delaunay triangulation,Pitteway triangulation
Conference
ISBN
Citations 
PageRank 
0-89871-490-7
18
1.15
References 
Authors
14
2
Name
Order
Citations
PageRank
Menelaos I. Karavelas122918.99
Leo J. Guibas25202536.33