Fast geometric approximation techniques and geometric embedding problems

ABSTRACT

Given an undirected n-vertex graph G and a set of n points in Rd, we wish to embed the vertices of G onto the points so as to minimize the total embedded edge length. Important special cases of this geometric embedding problem are those in which G is a binary tree, a cycle, or a star. We give fast approximation algorithms for embedding these graphs on the line and in the plane in several metrics. Our principal techniques are: a notion of “approximate geometric sorting” that can be computed in linear time, and fast approximation schemes for the minimum spanning tree problem in the plane. We expect that these approximation techniques can be applied to many geometric problems besides the embedding problem. We give the example of approximating the convex hull of a set of points in the plane.

REFERENCES

• AA: N. Alon and Y. Asar, Parallel Comparison Algorithms for Approximation Problems, Pmt. 29th IEEE Symp. on Foundations of Computer Science, 1988, 194-203.
• BFP: Jon Louis Bentley , Franco P. Preparata , Mark G. Faust, Approximation algorithms for convex hulls, Communications of the ACM, v.25 n.1, p.64-68, Jan. 1982 [doi>10.1145/358315.358392]
• BB: B. Bollobas and G. Brightwell, Graphs whose every transitive orientation contains almost every relation, Israel Journal of Mathematics 59 (1987) 112-128.
• CF: L. P. Chew and S. Fortune, Sorting helps for Voronoi diagrams, 13th Symp. on Mathematical Programming, Japan, 1988.
• C: N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Symp. on Algorithms and Complezity, Dept. of Computer Science, Carnegie-Mellon University, 1976.
• Chr: M. Chrobak, UC - Riverside, personal communication, 1989.
• Ch: F. R. K. Chung, On linear arrangements of trees, Comp. and Maths. with Appls. 10 (1984), 43-60.
• FT: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• GGJ: M. R. Garey , R. L. Graham , D. S. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.10-22, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803626]
• GJ: M.R. Garey and D.S. Johnson, Computers and Intractability, W.H. Freeman and Co., 1979.
• H: M. D. Hansen, Approximation Algorithms for Minimum Cost Embeddings of Graphs in the Plane, unpublished manuscript, MIT Laboratory for Computer Science, 1989.
• LL: F. T. Leighton and C. E. Leiserson, Wafer-scale integration of systolic arrays, IEEE l%ansactions on Computers C-34 (1985), 448-461.
• PY: Christos H. Papadimitriou , Mihalis Yannakakis, The complexity of restricted spanning tree problems, Journal of the ACM (JACM), v.29 n.2, p.285-309, April 1982 [doi>10.1145/322307.322309]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory