Computing geographic nearest neighbors using monotone matrix searching (preliminary version)

ABSTRACT

We present an &Ogr;(N log2 N) divide-and-conquer algorithm for solving the all pairs geographic nearest neighbor problem (GNN) for a set of N sites in the plane under any Lp metric, 1 ≤ p ≥ ∞. This algorithm uses the monotone matrix searching technique of Aggarwal et. al. In addition, our method yields an &Ogr;(N logd-1 N) expected time algorithm for the d-dimensional GNN problem. We also discuss the applications of GNN approach to rectilinear Steiner trees.

REFERENCES

• AK89: A. Aggarwal , D. Kravets, A linear time algorithm for finding all farthest neighbors in a convex polygon, Information Processing Letters, v.31 n.1, p.17-20, April 1989 [doi>10.1016/0020-0190(89)90103-8]
• AKMSW: A. Aggarwal, M. M. Klawe, S. Moran, P. Shor and R. Wilber, Geometric Applications of a Matrix-Searching Algorithm, Algorithmica 2, 195-208, 1987.
• AP88: A. Aggarwal and J. Park, Notes oll Searcl-ling ill Multidimensional Monotone Arrays, 29th Amzual IEEE ~mp. on Foundations of Co1~7p. Sci. 497-512, 1988.
• Ba83: A. Baratz, Algorithms for Integrated Circuit Signal Routing, Ph.D. Thesis MIT/LCS/TR-248, October 1983.
• Be80: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• BKST: J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
• CG88: R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73414]
• Cl87: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• GJ79: M. R. Garev and D. S. johnson, Computers and Intractability, Freeman, San Fransisco, 1979.
• GS83: L. J. Guibas and J. Stolfi, On Colnputing all North-east Nearest Neighbors in the L1 Metric, bTfo. Process. Lett. 17, 219-223, :/983.
• Ha66: M. Hannah, On Steiner's Problem with lZectilil~ear Dislance, J. SIAM Appl. Math. 14(2), 255-265, 1966.
• JK87: J. W. Jaromczyk , M. Kowaluk, A note on relative neighborhood graphs, Proceedings of the third annual symposium on Computational geometry, p.233-241, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41983]
• Ka88: Jyrki Katajaien, The region approach for computing relative neighborhood graphs in the Lp metric, Computing, v.40 n.2, p.147-161, May 1988 [doi>10.1007/BF02247943]
• Kl80: V. Klee, On the Complexity of ddimensional Voronoi diagrams. Arch. Math. 34, 75-80, 1980.
• KLP75: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• Ri89: D. Richards, Fast Heuristic Algorithms for Rectilinear Steiner Trees, Algorithmica 4, 191-207, 1989.
• SH75: M. I. Shamos and D. Hoey, Closest-Point Problelns, 16th Ann. IEEE Syrup. on Foundations of Comp. Sci. 151-162, 1975.
• Su83: Kenneth J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, Journal of the ACM (JACM), v.30 n.3, p.428-448, July 1983 [doi>10.1145/2402.322386]
• WCR89: Y. C. Wee, S. Chaiken and S. S. Ravi, Some Applications of the Geographic Nearest Neighbor Approach, To appear in l'roc, of the 27th Annual Allerton Conference, 1989.
• WCR89: Y. C. Wee, S. Chaiken and S. S. Ravi, A Fast Heuristic Algorithm for the Rectilinear Steiner Trees, in preparation, 1989.
• WCW88: Y. C. Wee, S. Chaiken and D. E. Witlard, A Linear Space Approximation to the Complete Graph and its Applications to Proximity Problems, Technical Report No. 88-30, .grate Utziv. of N.Y. at Albwo,, 1988.
• WW88: D. E. Willard , Y. C. Wee, Quasi-Valid range querying and its implications for nearest neighbor problems, Proceedings of the fourth annual symposium on Computational geometry, p.34-43, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73398]
• Ya82: A. C. Yao, On constructing Minimum Spanning Trees in k-dimensional Spaces and Related Problems, SIAM .1. Comput. 11(4), 721-736, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms