An expander-based approach to geometric optimization

ABSTRACT

We present a new approach to problems in geometric optimization that are traditionally solved using the parametric searching technique of Megiddo. Our new approach is based on expander graphs and is conceptually much simpler and has more explicit geometric flavor. It does not require parallelization or randomization, and it exploits recent range-searching techniques of Matousˇek and others. We exemplify the technique on three problems, the slope selection problem, the planar distance selection problem, and the planar two-center problem. For the first problem we develop an O(n log3n)) solution, which, although suboptimal, is very simple. The second and third problems are more typical examples of our approach. Our solutions have, respectively, running time O(n4/3 log3+&dgr; n), for any &dgr; > 0, and O(n2 log3 n), comparable with the respective solutions of [2, 5].

REFERENCES

• 1: P.K. AgarwM, personM communication.
• 2: 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]
• 3: Pankaj K. Agarwal , Alon Efrat , Micha Sharir , Sivan Toledo, Computing a segment center for a planar point set, Journal of Algorithms, v.15 n.2, p.314-323, Sept. 1993 [doi>10.1006/jagm.1993.1043]
• 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. Rept. 90-58, DIMACS, Rutgers University, August 1990. (Also to appear in Aigorithmica.)
• 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: Miklos Ajtai , Nimrod Megiddo, A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.327-338, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129744]
• 8: N. Alon and J. Spencer, The Probabilistic Method, Wiley-Interscience. New York, 1992.
• 9: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142702]
• 10: B. Chazelle, M. Sharir and E. Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Algorithmica 12 (1992), 407-429.
• 11: B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
• 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: M. Dillencourt, D. Mount and N. Netanyahu, A randomized algorithm for slope selection, Int. J. Comput. Geom. and Appls 2 (1992), 1-27.
• 16: D. Haussler and E. Welzl, Epsilon nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127- 151.
• 17: John Hershberger , Subhash Suri, Finding tailored partitions, Journal of Algorithms, v.12 n.3, p.431-463, Sept. 1991 [doi>10.1016/0196-6774(91)90013-O]
• 18: M.J. Katz and M. Sharir, Optimal slope selection via expanders, manuscript.
• 19: A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
• 20: G.A. Margulis, Explicit group-theoretical constructions of combinatorial schemes and their applications to the design of expanders and superconcentrators, Problemy Peredachi In/ormatsii 24 (1988), 51-60 (in Russian). English translation in Problems of In/orma. tion Transmission 24, 39-46.
• 21: 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]
• 22: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 23: Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142732]
• 24: J. Matou~ek and O. Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, manuscript.
• 25: 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]
• 26: 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]
• 27: L. Valiant, Parallelism in comparison problems, SIAM J. Computing 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Verification