Diameter, width, closest line pair, and parametric searching

ABSTRACT

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improve solutions for them. We obtain, for any fixed &egr; > 0, an O(n1+&egr;) algorithm for computing the diameter of a point set in 3-space, an O(n8/5+&egr;) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic. We also look at the problem of computing the k-th smallest slope formed by the lines joining n points in the plane. In 1989 Cole, Salowe, Steiger, and Szemere´di gave an optimal but very complicated O(n log n) solution based on Megiddo's technique. We follow a different route and give a very simple O(n log2 n) solution which bypasses parametric searching altogether.

REFERENCES

• 1: Pankaj K. Agarwal , Boris Aronov , Micha Sharir , Subhash Suri, Selecting distances in the plane, Proceedings of the sixth annual symposium on Computational geometry, p.321-331, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98597]
• 2: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
• 3: P.K. Agarwal, A. Efrat, M. Sharir and S. Toledo, Computing a segment center for a planar pc,int set, manuscript, 1991.
• 4: Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
• 5: P.K. Agarwal and M. Sharir, Planar geometric location problems, Tech. Kept. 90-58, DIMACS, Rutgers University, August 1990. (Also to appear in Algorithmica.)
• 6: Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
• 7: Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
• 8: Bernard Chazelle, An optimal convex hull algorithm and new results on cuttings (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.29-38, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185345]
• 9: B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
• 10: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
• 11: B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains, submitted to Algorithmica.
• 12: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 13: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 14: Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989 [doi>10.1137/0218055]
• 15: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• 16: M. Dillencourt, D. Mount, N. Netanyahu A randomized algorithm for slope selection, fnt. J. Comput. Geom. and Appl., to appeal'.
• 17: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 18: D. Haussler and E. Welzl, e-nets and simplex range queries, Dzscrete Comput. Geom. 2 (1987), 127-151.
• 19: Michael E. Houle , Godfried T. Toussaint, Computating the width of a set, Proceedings of the first annual symposium on Computational geometry, p.1-7, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323234]
• 20: D. Kirkpatrick, Optimal search in planar subdivisions, SIAM J. Computing 12 (1983), 28-35.
• 21: Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109649]
• 22: Jiři Matoušek, Randomized optimal algorithm for slope selection, Information Processing Letters, v.39 n.4, p.183-187, Aug. 30, 1991 [doi>10.1016/0020-0190(91)90177-J]
• 23: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• 24: J. Matou~ek, Computing the center of planar point sets, Discrete and Computational Geometry DIMACS, Amer. Math. Soc., eds, J.E. Goodman, R. Pollack, W. Steiger (1991), 221-230.
• 25: Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
• 26: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 27: N. Naor and M. Sharir, Computing a, point in the center of a point set in three dimensions. Proc. 2nd Canadian Conference on Computational Geometry, 1990, 10-13.
• 28: W. Steiger, Private communication, 1991.
• 29: Andrew Stein , Michael Werman, Finding the repeated median regression line, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.409-413, September 1992, Orlando, Florida, United States
• 30: Sivan Toledo, Extremal polygon containment problems, Proceedings of the seventh annual symposium on Computational geometry, p.176-185, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109668]
• 31: L. Valiant, Parallelism in comparison problems, SIAM .L Computzng 4 (1975), 348-355.

INDEX TERMS

Primary 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

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

General Terms:
Algorithms, Theory