caa a22 4500 469075198 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920101xx s 000 0 eng 10.1007/BF02187821 doi (NATIONALLICENCE)springer-10.1007/BF02187821 Classes of graphs which approximate the complete euclidean graph [Elektronische Daten] [J. Keil, Carl Gutwin] 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. Springer-Verlag New York Inc., 1992 Keil J. Department of Computational Science, University of Saskatchewan, S7N 0W0, Saskatoon, Canada aut Gutwin Carl Department of Computational Science, University of Saskatchewan, S7N 0W0, Saskatoon, Canada aut Discrete & Computational Geometry Springer New York 7/1(1992-01-01), 13-28 0179-5376 7:1<13 1992 7 454 https://doi.org/10.1007/BF02187821 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187821 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Keil J. Department of Computational Science, University of Saskatchewan, S7N 0W0, Saskatoon, Canada aut NATIONALLICENCE 700 1- Gutwin Carl Department of Computational Science, University of Saskatchewan, S7N 0W0, Saskatoon, Canada aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/1(1992-01-01), 13-28 0179-5376 7:1<13 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer