Abstract
A line intersecting all polyhedra in a setℬ is called a “stabber” for the setℬ. This paper addresses some combinatorial and algorithmic questions about the setℒ(ℬ) of all lines stabbingℬ. We prove that the combinatorial complexity ofℒ(ℬ) has an\(O(n^3 2^{c\sqrt {\log n} } )\) upper bound, wheren is the total number of facets inℬ, andc is a suitable constant. This bound is almost tight. Within the same time bound it is possible to determine if a stabbing line exists and to find one.
Article PDF
Similar content being viewed by others
References
P. K. Agarwal. A deterministic algorithm for partitioning arrangements of lines and its applications. InProceedings of the 5th ACM Symposium on Computational Geometry, pages 11–22, 1989.
A. Amenta. Finding a line transversal of axial objects in three dimensions. To appear inProceedings of the 3rd ACM Symposium on Discrete Algorithms, 1991.
D. Avis, J. M. Roberts, and R. Wenger. Lower bounds for line stabbing.Information Processing Letters, 33:59–62, 1989.
D. Avis and R. Wenger. Algorithms for line transversals in space. InProceedings of the 3rd Annual Symposium on Computational Geometry, pages 300–307, 1987.
D. Avis and R. Wenger. Polyhedral line transversals in space.Discrete Computational Geometry, 3:257–265, 1988.
K. Borsuk.Multidimensional Analytic Geometry. Polish Scientific, 1969.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi. Lines in space: Combinatorics and applications. Technical Report UIUCDCS-R-90-1569, Department of Computer Science, University of Illinois at Urbana-Champaign, February 1990.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Lines in space: combinatorics, algorithms and applications. InProceedings of the 21st Symposium on Theory of Computing, pages 382–393, 1989.
K. L. Clarkson. New applications of random sampling in computational geometry.Discrete Computational Geometry, 2:195–222, 1987.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987.
H. Edelsbrunner and M. Sharir. The maximum number of ways to stabn convex non-intersecting objects in the plane is 2n − 2. Robotics lab 101, Courant Institute, March 1987.
W. V. D. Hodge and D. Pedoe.Methods of Algebraic Geometry. Cambridge University Press, Cambridge, 1952.
M. Hohmeyer and S. Teller. Stabbing isothetic boxes and rectangles inO(n logn) time. Technical Report 91/634, University of California, Berkeley, May 1991.
J. W. Jaromczyk and M. Kowaluk. Skewed projections with an application to line stabbing inR 3. InProceedings of the 4th Annual Symposium on Computational Geometry, pages 362–370, 1988.
J. Matoušek. Construction ofɛ-nets. InProceedings of the 5th ACM Symposium on Computational Geometry, pages 1–10, 1989.
J. Matoušek. Cutting hyperplane arrangements. InProceedings of the 6th ACM Symposium on Computational Geometry, pages 1–9, 1990.
N. Megiddo. Personal communication, 1991.
M. McKenna and J. O'Rourke. Arrangements of lines in 3-space: a data structure with applications. InProceedings of the 4th Annual Symposium on Computational Geometry, pages 371–380, 1988.
M. Pellegrini. Stabbing and ray shooting in 3-dimensional space. InProceedings of the 6th Annual Symposium on Computational Geometry, pages 177–187, 1990.
M. Pellegrini. Combinatorial and algorithmic analysis of stabbing and visibility problems in 3-dimensional space. Ph.D. thesis, Courant Institute of Mathematical Sciences, New York University, February 1991.
D. M. H. Sommerville.Analytical Geometry of Three Dimensions. Cambridge University Press, Cambridge, 1951.
J. Stolfi. Primitives for computational geometry. Technical Report 36, Digital SRC, 1989.
Author information
Authors and Affiliations
Additional information
The research of M. Pellegrini was partially supported by Eni and Enidata within the AXL project, and by NSF Grant CCR-8901484. A preliminary version appeared in theProceedings of the Second ACM-SIAM Symposium on Discrete Algorithms, pp. 24–31.
Rights and permissions
About this article
Cite this article
Pellegrini, M., Shor, P.W. Finding stabbing lines in 3-space. Discrete Comput Geom 8, 191–208 (1992). https://doi.org/10.1007/BF02293043
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02293043
