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

algorithmDelaunay triangulationspannerbounded degreediamond triangulation

Mathematics Subject Classification ID

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

Related Items (11)

On plane geometric spanners: a survey and open problems ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ On bounded degree plane strong geometric spanners ⋮ Improved spanning ratio for low degree plane spanners ⋮ Improved local algorithms for spanner construction ⋮ Lattice Spanners of Low Degree ⋮ 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 ⋮ Lattice spanners of low degree ⋮ There are plane spanners of degree 4 and moderate stretch factor

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

This page was built for publication: DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE