Line transversals of convex polyhedra in R3

ABSTRACT

We establish a bound of O(n²k^1+ε), for any ε > 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in R³ with a total of n facets, and present a randomized algorithm which computes the boundary of T in comparable expected time. Thus, when k ≪ n, the new bounds on the complexity (and construction cost) of T improve upon the previously best known bounds, which are nearly cubic in n.

To obtain the above result, we study the set T_l0 of line transversals which emanate from a fixed line l₀, establish an almost tight bound of O(nk^1+ε) on the complexity of T_l0, and provide a randomized algorithm which computes T_l0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of T_l0, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of P are pairwise disjoint: the case where l₀ is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to l₀.

REFERENCES

• 1: Pankaj K. Agarwal, On stabbing lines for convex polyhedra in 3D, Computational Geometry: Theory and Applications, v.4 n.4, p.177-189, Aug. 1994 [doi>10.1016/0925-7721(94)90016-7]
• 2: P. K. Agarwal, B. Aronov and M. Sharir, Line transversals of balls and smallest enclosing cylinders in three dimensions, Discrete Comput. Geom. 21(3) (1999), 373--388.
• 3: P. K. Agarwal, O. Schwarzkopf and M. Sharir, The overlay of lower envelopes in 3-space and its applications, Discrete Comput. Geom. 15 (1996), 1--13.
• 4: Pankaj K. Agarwal , Micha Sharir, Ray Shooting Amidst Convex Polyhedra and PolyhedralTerrains in Three Dimensions, SIAM Journal on Computing, v.25 n.1, p.100-116, Feb. 1996 [doi>10.1137/S0097539793244368]
• 5: Boris Aronov , Micha Sharir , Boaz Tagansky, The Union of Convex Polyhedra in Three Dimensions, SIAM Journal on Computing, v.26 n.6, p.1670-1688, Dec. 1997 [doi>10.1137/S0097539793250755]
• 6: Boris Aronov , Shakhar Smorodinsky, Geometric Permutations Induced by Line Transversals through a Fixed Point, Discrete & Computational Geometry, v.34 n.2, p.285-294, August 2005 [doi>10.1007/s00454-005-1174-2]
• 7: David Avis , Rephael Wenger, Polyhedral line transversals in space, Discrete & Computational Geometry, v.3 n.3, p.257-265, Jan., 1988 [doi>10.1007/BF02187911]
• 8: Hervé Brönnimann , Olivier Devillers , Vida Dujmović , Hazel Everett , Marc Glisse , Xavier Goaoc , Sylvain Lazard , Hyeon-Suk Na , Sue Whitesides, Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra, SIAM Journal on Computing, v.37 n.2, p.522-551, May 2007 [doi>10.1137/S0097539705447116]
• 9: H. Brönnimann , H. Everett , S. Lazard , F. Sottile , S. Whitesides, Transversals to Line Segments in Three-Dimensional Space, Discrete & Computational Geometry, v.34 n.3, p.381-390, September 2005 [doi>10.1007/s00454-005-1183-1]
• 10: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir and J. Stolfi, Lines in space: Combinatorics and algorithms, Algorithmica 15 (1996), 428--447.
• 11: 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]
• 12: Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
• 13: Herbert Edelsbrunner , Micha Sharir, The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n - 2, Discrete & Computational Geometry, v.5 n.1, p.35-42, Jan. 1990 [doi>10.1007/BF02187778]
• 14: Alon Efrat , Leonidas J. Guibas , Olaf A. Hall-Holt , Li Zhang, On incremental rendering of silhouette maps of a polyhedral scene, Computational Geometry: Theory and Applications, v.38 n.3, p.129-138, October, 2007 [doi>10.1016/j.comgeo.2006.12.003]
• 15: J. E. Goodman, R. Pollack and R. Wenger, Geometric transversal theory, in New Trends in Discrete and Computational Geometry, J. Pach (Ed.), Springer Verlag, Berlin, 1993, pp. 163--198.
• 16: D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions, with applications to visbility in terrains, Discrete Comput. Geom. 12 (1994), 313--326.
• 17: H. Kaplan, N. Rubin and M. Sharir, Linear data structures for fast ray shooting amidst convex polyhedra, Algorithmica, to appear. Also in Proc. 15th Europ. Sympos. Algo., 2007, 287--298.
• 18: H. Kaplan, N. Rubin and M. Sharir, Line transversals of convex polyhedra in R³, http://www.cs.tau.ac.il/~rubinnat/TransPoly.pdf. Also see arXiv:0807.1221.
• 19: M. Katchalski, T. Lewis and J. Zaks, Geometric permutations for convex sets, Discrete Math. 54 (1985), 271--284.
• 20: M. Katchalski , T. Lewis , A. Liu, The different ways of stabbing disjoint convex sets, Discrete & Computational Geometry, v.7 n.2, p.197-206, 1992 [doi>10.1007/BF02187836]
• 21: M. J. Katz and K. R. Varadarajan, A tight bound on the number of geometric permutations of convex fat objects in R^d, Discrete Comput. Geom. 26(4) (2001), 543--548.
• 22: V. Koltun and M. Sharir, The partition technique for overlays of envelopes, SIAM J. Comput. 32(4) (2003), 841--863.
• 23: M. McKenna , J. O'Rourke, Arrangements of lines in 3-space: a data structure with applications, Proceedings of the fourth annual symposium on Computational geometry, p.371-380, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73431]
• 24: M. Pellegrini, Lower bounds on stabbing lines in 3-space, Computational Geometry: Theory and Applications, v.3 n.1, p.53-58, June 1993 [doi>10.1016/0925-7721(93)90030-A]
• 25: M. Pellegrini , P. W. Shor, Finding stabbing lines in 3-space, Discrete & Computational Geometry, v.8 n.2, p.191-208, 1992 [doi>10.1007/BF02293043]
• 26: Marco Pellegrini, Ray shooting and lines in space, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 27: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 28: S. Smorodinsky, J. S. B. Mitchell and M. Sharir, Sharp bounds on geometric permutations of pairwise disjoint balls in R^d, Discrete Comput. Geom. 23(2) (2000), 247--259.
• 29: D. Sommerville, Analytical Geometry in Three Dimensions, Cambridge University Press, Cambridge, 1951.
• 30: Rephael Wenger, Permutations for convex sets, Discrete & Computational Geometry, v.5 n.1, p.27-33, Jan. 1990 [doi>10.1007/BF02187777]
• 31: Rephael Wenger, Helly-type theorems and geometric transversals, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms