Classes of graphs which approximate the complete Euclidean graph (Q1186079)

A euclidean graph is a graph with points of the plane as vertices and edge-lengths the euclidean distance between the endpoints. An euclidean graph \(G\) \(t\)-approximates the complete euclidean graph (t-ACEG) if for any pair of vertices the shortest path length in \(G\) is within \(t\) times their euclidean distance. In this paper it is first shown that the graph corresponding to the Delaunay triangulation (dual to the Voronoi diagram) is \(2\pi/3\cos(\pi/6)\) \((\approx 2,42)\) -ACEG. An example is known for which this graph is \(\pi/2\approx 1.57\). The authors then define a new class of euclidean graphs, the fixed angle \(\Theta\)-graphs, for any \(\Theta=2\pi/k\) \((k>8)\), which are \(1/(\cos \Theta-\sin \Theta)\)-ACEG (e.g. for \(k=40\) we have \(\pm 1.20\)). The interest is that this bound decreases with increasing \(k\) and that the corresponding \(\Theta\)-graph may be constructed for any fixed \(k\) in \(0(n\log n)\) time (\(n\)=number of vertices) by a plane sweep algorithm.