Stabbing pairwise disjoint translates in linear time

ABSTRACT

In general, finding a line stabber for a family of n objects in the plane takes &ohgr;(n log n) time. However, we show how to find a line stabber for a family of n pairwise disjoint convex translates in the plane in linear time. Our algorithm still runs in optimal &Ogr; (n log n) time when the translates are not pairwise disjoint.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Mikhail Atallah , Chanderjit Bajaj, Efficient algorithms for common transversals, Information Processing Letters, v.25 n.2, p.87-91, 6 May 1987 [doi>10.1016/0020-0190(87)90226-2]
• 3: Avis, D. and Do&as, M., 'Algorithms for high dimensional stabbing problems,' Technical Report SOCS 87.2, McGill University, Montreal (1987).
• 4: Avis, D., Robert, J.-M., and Wenger, R., 'Lower bounds for line stabbing,' manuscript.
• 5: Dyer, M.E., 'Linear time algorithms for twoand three-variable linear programs,' SIAM J. Computing, 13 pp. 31-45 (1984).
• 6: Edelsbrunner, H., 'Finding transversals for sets of simple geometric figures,' Theoretical Computer Science 35 pp. 55-69 (1985).
• 7: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 8: Edelsbrunner, E., Guibas, L. J. and Sharir, M., 'The upper envelope of piecewise linear functions: algorithms and applications,' Report No. UIUCDCS-R-87-1390, University of Illinois (1987).
• 9: Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E. and Wood, D., 'Stabbing line segments,' BIT 22 pp. 274-281 (1982).
• 10: Edelsbrunner, H., and Sharir, M., 'The maximum number of ways to stab n convex non-intersecting objects in the plane is 2n - 2,' Technical Report UIUCDCS-R-87- 1322, University of Illinois.
• 11: Hadwiger, H., Debrunner, H. and Klee, V., Combinatorial Geometry in the Plane, Holt, Rinehart and Winston (1964).
• 12: Hershberger, J., 'Finding the upper envelope of n line segments in O(nZogn) time', manuscript.
• 13: Katchalski, M., 'A conjecture of Griinbaum on common transversals,' Math. Stand. 59 pp. 192-198 (1986).
• 14: Katchalski, M., Lewis, T. and Liu, A., 'Geometric permutations and common transversals,' Discrete and Computational Geometry 1 pp. 371-377 (1986).
• 15: M. Katchalski , T. Lewis , A. Liu, Geometric permutations of disjoint translates of convex sets, Discrete Mathematics, v.65 n.3, p.249-259, July 1987 [doi>10.1016/0012-365X(87)90057-4]
• 16: Katchalski,.M., L ewis, T. and Zaks, J., 'Geometric permutations for convex sets,' Discrete Mathematics 54 pp. 271-284 (1985).
• 17: David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
• 18: Lewis, T., 'Two counterexamples concerning transversals for convex subsets of the plane,' Geometriae Dedicata 9 pp. 461-465 (1980).
• 19: Megiddo, N., 'Linear-time algorithms for linear programming in R3 and related problems,' SIAM J. Computing 12 pp. 759-776 (1983).
• 20: 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]
• 21: Joseph O'Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM, v.24 n.9, p.574-578, Sept. 1981 [doi>10.1145/358746.358758]
• 22: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 23: R. Seidel, Output-size sensitive algorithms for constructive problems in computational geometry, Cornell University, Ithaca, NY, 1987
• 24: H. Tverberg, Proof of Gru¨nbaum's conjecture on common transversals for translates, Discrete & Computational Geometry, v.4 n.3, p.191-203, March 1989 [doi>10.1007/BF02187722]
• 25: Rephael Wenger, A generalization of Hadwiger's transversal theorem to intersecting sets, Discrete & Computational Geometry, v.5 n.4, p.383-388, Jul. 1990 [doi>10.1007/BF02187799]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

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

General Terms:
Algorithms, Theory