Classes of graphs which approximate the complete euclidean graph |
| |
Authors: | J Mark Keil Carl A Gutwin |
| |
Institution: | (1) Department of Computational Science, University of Saskatchewan, S7N 0W0 Saskatoon, Canada |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|