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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Benson, R.,Euclidean Geometry and Convexity, McGraw-Hill, New York, 1966.
Chew, P., There is a planar graph almost as good as the complete graph,Proceedings of the Second Symposium on Computational Geometry, Yorktown Heights, NY, 1986, pp. 169–177.
Chew, P., There are planar graphs almost as good as the complete graph,Journal of Computer and System Sciences,3(9) (1989), 205–219.
Dobkin, D., S. Friedman, and K. Supowit, Delaunay graphs are almost as good as complete graphs,Proceedings of the 28th Annual Symposium on Foundations of Computing, Los Angeles, CA, 1987, pp. 20–26.
Peleg, D., and A. A. Schaffer, Graph spanners,Journal of Graph Theory,13(1) (1989), 99–116.
Preparata, F., and M. Shamos,Computational Geometry: an Introduction, Springer-Verlag, New York, 1985.
Sedgewick, R., and J. Vitter, Shortest paths in Euclidean graphs,Algorithmica,1(1) (1986), 31–48.
Wee, Y. C., Chaiken, S., and Willard D. E., General metrics and angle restricted Voronoi diagrams, Presented at the First Canadian Conference on Computational Geometry, Montreal, August 1989.
Yao, A. C., On constructing minimum spanning trees ink-dimensional spaces and related problems,SIAM Journal on Computing,11 (1982), 721–736.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Keil, J.M., Gutwin, C.A. Classes of graphs which approximate the complete euclidean graph. Discrete Comput Geom 7, 13–28 (1992). https://doi.org/10.1007/BF02187821
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187821