Classes of graphs which approximate the complete euclidean graph

• DOI: 10.1007/bf02187821
• Publication Date: 2005-10-29T08:58:18Z
• Authors: J. Mark Keil; Carl A. Gutwin
• Keywords: 510.mathematics; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; Article

LetS be a set ofN points in the Euclidean plane, and letd(p, q) be the Euclidean distance between pointsp andq inS. LetG(S) be a Euclidean graph based onS and letG(p, q) be the length of the shortest path inG(S) betweenp andq. We say a Euclidean graphG(S)t-approximates the complete Euclidean graph if, for everyp, q ?S, G(p, q)/d(p, q) ≤t. In this paper we present two classes of graphs which closely approximate the complete Euclidean graph. We first consider the graph of the Delaunay triangulation ofS, DT(S). We show that DT(S) (2?/(3 cos(?/6)) ? 2.42)-approximates the complete Euclidean graph. Secondly, we define?(S), the fixed-angle?-graph (a type of geometric neighbor graph) and show that?(S) ((1/cos?)(1/(1?tan?)))-approximates the complete Euclidean graph.