DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE

DOI10.1142/S0218195909002861zbMath1167.65335MaRDI QIDQ3636312

Daming Xu, Prosenjit Bose, Michiel H. M. Smid

Publication date: 30 June 2009

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

algorithm; Delaunay triangulation; spanner; bounded degree; diamond triangulation

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Lower Bounds on the Dilation of Plane Spanners, Lower Bounds on the Dilation of Plane Spanners, Vertex fault-tolerant spanners for weighted points in polygonal domains, Vertex Fault-Tolerant Geometric Spanners for Weighted Points, On plane geometric spanners: a survey and open problems, On bounded degree plane strong geometric spanners, Improved local algorithms for spanner construction, Improved spanning ratio for low degree plane spanners, There are plane spanners of degree 4 and moderate stretch factor, Lattice Spanners of Low Degree, Lattice spanners of low degree

Cites Work

• Delaunay graphs are almost as good as complete graphs
• Constructing plane spanners of bounded degree and low weight
• Classes of graphs which approximate the complete Euclidean graph
• There are planar graphs almost as good as the complete graph
• Approximating geometric bottleneck shortest paths
• Geometric Spanner Networks
• Online Routing in Triangulations
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER