A probabilistic algorithm for the post office problem

ABSTRACT

The post office problem is the following: points in d-dimensional space, so that given an arbitrary point p, the closest points in S to p can be found quickly. We consider the case of this problem where the Euclidean norm is the measure of distance. The previous best algorithm for this problem for d>2 requires &Ogr;(n2d+1) preprocessing time to build a data structure allowing an &Ogr;(log n query time. We will show that a data structure can be built in expected &Ogr;(n(d-1)(1+k)) time, for any fixed k;>&Ogr;, so that closest-point queries can be answered in &Ogr;(log n) worstcase time. (The constant factors depend on d and k.) The algorithm employs random sampling, so the expected time holds for any set of points. A variant of this algorithm (for the variant problem where only one closest point of S to the query point is desired) requires &Ogr;(n⌈d/2⌉) &ogr;(n⌈d/2⌉) preprocessing time for &ogr;(nt) worst-case query time, for any fixed &egr;>0. These results approach the &OHgr;(n⌈d/2⌉) preprocessing time required for any algorithm constructing the Voronoi diagram of the input points. Implementation of these algorithms requires not too much more than a random sampling procedure and a procedure for constructing the Voronoi diagram of that random sample.

REFERENCES

• AvB: D. Avis and B. K. Bhattacharya. Algorithms for computing d-dimensional Voronoi diagrams and their duals. Advances in Computing Research, Volume 1 (1983), pp. 159-180.
• Bha: Binay K. Bhattacharya, Application of computational geometry to pattern recognition problems, 1982
• Bro1: Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
• Bro2: K. Q. Brown. Voronoi diagrams from convex hull. Information Processing Letters, Volume 9 (1979), pp.223-228.
• BWY: Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
• Cla: K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
• ChK: Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
• DoL: D. Dobkin and R. J. Lipton. Multidimensional searching problems. SIAM J. Computing, Volume 5 (1976), pp. 181-186.
• Dye: M. E. Dyer. On a multidimensional search technique and its application to the Euclidean one-centre problem. Unpublished manuscript.
• EGS: H. Edelsbrunncr, L. Guibas, and J. Stoifi. Optimal point location in a planar subdivision.
• Gil: E. N. Gilbert. Random subdivisions of space into crystals. Ann, Math, Slat. Volume 33 (1962), pp. 958-972.
• Gru: B. Gr/inbaum. Convex Polytopes. Wiley, New York, 1967.
• Guy: R. K. Guy. A couple of cubic conundrums. Arneri. can Math. Monthly, Volume 91 (1984), pp. 624-629.
• Kir: D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Computing, Volume 12 (1983), pp. 28-35.
• Kl1: V. K!ee. Some characterizations of convex polyhedra. ,4eta Mathematica, Volume 102 (1959), pp. 79-107.
• Kl2: V. Klee. On the complexity of d-dimensional Voronoi diagrams. Arch. Math., Volume 34 (1980), pp. 75- 80.
• LH: C. L. Lawson and R. J. Hanson. Solving Least Squares Problems. Prentice-Hall, 1974.
• LT: R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. Proc. 18th IEEE Symp. on FOCS, 0977), pp. 162-169.
• McM: P. McMullen. The maximum number of faces of a convcx polytope. Mathematika, Volume 17 (1970), pp. 179-184.
• Meg: Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
• Sha: Michael Ian Shamos, Computational geometry., 1978
• Sei1: R. Seidel. A convex hull algorithm optimal for point sets in cvcn dimensions. MSc Thesis, Univ. British Columbia, 1981.
• Sei2: R. Seidel. On the size of the closest point Voronoi diagrams. Institute fiir lnformationsverarbeitung, Technische Univcrsit/it Graz und Ostcrreichissche Computergesellschaft, Austria No 94, 1982.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory, Verification