Applications of parametric searching in geometric optimization

ABSTRACT

We present several applications in computational geometry of Megiddo's parametric searching technique. These applications include; (1) Finding the minimum Hausdorff distance in the Euclidean metric between two polygonal regions under translation; (2) Computing the biggest line segment that can be placed inside a simple polygon; (3) Computing the smallest width annulus that can contain a given set of points in the plane; (4) Solving the 1-segment center problem—given a set of points in the plane, find a placement for a given line segment (under translation and rotation) which minimizes the largest distance from the segment to the given points; (5) Given a set of n points in 3-space, finding the largest radius r such that if we place a ball of radius r around each point, no segment connecting a pair of points is intersected by a third ball. Besides obtaining efficient solutions to all these problems (which, in every case, either improve considerably previous solutions or are the first non-trivial solutions to these problems), our goal is to demonstrate the versatility of the parametric searching technique.

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: K P Agarwal , Alon Efrat , Micha Sharir , Sivan Toledo, Computing a Segment-Center for a Planar Point Set, Duke University, Durham, NC, 1991
• 3: K P Agarwal , Jiri Matousek, Ray Shooting and Parametric Search, Duke University, Durham, NC, 1991
• 4: P.K. Agarwal and M. Sharir, Planar geometric location problems, Tech. Rept. 90-58, DIMACS, Rutgers University, August 1990. (Also to appear in A19orithmiea.)
• 5: Pankaj K. Agarwal , Micha Sharir, Counting circular arc intersections, Proceedings of the seventh annual symposium on Computational geometry, p.10-20, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109650]
• 6: P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
• 7: P.K. Agarwal, M. Sharir and S. Toledo, Applications of parametric searching in geometric optimization, manuscript, 1991.
• 8: A. Aggarwal , S. Suri, Computing the longest diagonal of a simple polygon, Information Processing Letters, v.35 n.1, p.13-18, June 1990 [doi>10.1016/0020-0190(90)90167-V]
• 9: Helmut Alt , Bernd Behrends , Johannes Blömer, Approximate matching of polygonal shapes (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.186-193, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109669]
• 10: M. J. Atallah , R. Cole , M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms, SIAM Journal on Computing, v.18 n.3, p.499-532, June 1989 [doi>10.1137/0218035]
• 11: J.L. Bentley and T. Ottmann, Algorithms for reporting and counting geometric intersections, IEEE Trans. on Computers C-28 (1979), 643-647.
• 12: B. Chazelle, The polygon containment problem, in Advances in Comporting Research, VoL I: Computational Geometry, (F.P. Preparata, Ed.), JAI Press, Greenwich, Connecticut (1983), pp. 1-33.
• 13: 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]
• 14: B. Chazelle, H. Edelsbrulmer, L. Guibas and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains, to appear in Algorithmica.
• 15: B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, Diameter, width, closest line-pair, and parametric searching, in preparation.
• 16: B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
• 17: B. Chazelle , M. Sharir, An algorithm for generalized point location and its applications, Journal of Symbolic Computation, v.10 n.3-4, p.281-309, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80065-X]
• 18: 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]
• 19: 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]
• 20: 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]
• 21: H. Ebara, N. Fukuyama, H. Nakano and Y. Nakanishi, Roundness algorithms using the Voronoi diagrams, First Canadian Con}. Computational Geometry, 1989.
• 22: Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
• 23: G. Frederickson and D. Johnson, Finding the kth shortest paths and p-centers by generating and searching good data structures, J. Algorithms 4 (1983), 61-80.
• 24: Michael T. Goodrich, Using approximation algorithms to design parallel algorithms that may ignore processor allocation (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.711-722, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185439]
• 25: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 26: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
• 27: Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
• 28: Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109670]
• 29: Matthew J. Katz , Mark H. Overmars , Micha Shairr, Efficient hidden surface removal for objects with small union size, Proceedings of the seventh annual symposium on Computational geometry, p.31-40, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109652]
• 30: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 31: H. hnai, D.T. Lee, and C. Yang, l-Segment covering problem, 1st Canadian Con}. Computational Geometry, 1989. Also, manuscript, 1991.
• 32: D. Leven and M. Shaxir, On the number of critical free contacts of a convex polygonal object moving in twodimensional polygonal space, Discrete Comput. Geom. 2 (1987), 255-270.
• 33: 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]
• 34: 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]
• 35: 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]
• 36: 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]
• 37: N. Megiddo, Linear-time algorithms for linear program- 12 (1983), 720-732.
• 38: 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]
• 39: N. Naor and M. Sharir, Computing the center of a point set in three dimensions, Proc. 2nd Canadian Conf. on Computalional Geometry (1990), pp. 10-13.
• 40: 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]
• 41: R. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm, SIAM J. Comp. 14 (1985), 862-874.
• 42: 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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory, Verification