×

Polyhedral line transversals in space. (English) Zbl 0679.68130

Summary: Algorithms are developed for determining if a set of polyhedral objects in \(R^ 3\) can be intersected by a common transversal (stabbing) line. It can be determined in 0(n log n) time if a set of n line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total of n vertices, we give an \(0(n^ 4\log n)\) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.

MSC:

68R99 Discrete mathematics in relation to computer science
52A35 Helly-type theorems and geometric transversal theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Avis, D., Diameter Partitioning,Discrete and Computational Geometry, Vol. 1, pp. 265-276, 1986. · Zbl 0594.52003 · doi:10.1007/BF02187699
[2] Avis, D. and Doskas, M., Algorithms for High-Dimensional Stabbing Problems, Technical Report SOCS 87.2, McGill University, Montreal, January 1987.
[3] Avis, D. and Wenger, R., Algorithms for Line Stabbers in Space,Proceedings of the 3rd ACM Conference on Computational Geometry, pp. 300-307, Waterloo, 1987.
[4] Borsuk, K.,Multidimensional Analytic Geometry, Polish Scientific Publishers, Warsaw, 1969. · Zbl 0189.21201
[5] Danzer, L., Grunbaum, B., and Klee, V.,Helly’s Theorem and Its Relatives, Proceedings of Symposia in Pure Mathematics, pp. 100-181, American Mathematical Society, Providence, RI, 1963. · Zbl 0132.17401
[6] Dobkin, D. and Kirpatrick, D., Fast Detection of Polyhedral Intersection,Theoretical Computer Science, Vol. 27, pp. 241-253, 1983. · Zbl 0553.68033 · doi:10.1016/0304-3975(82)90120-7
[7] Edelsbrunner, H., Finding Transversals for Sets of Simple Geometric Figures,Theoretical Computer Science, Vol. 35, pp. 55-69, 1985. · Zbl 0604.68080 · doi:10.1016/0304-3975(85)90005-2
[8] Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D., Stabbing Line Segments,BIT, Vol. 22, pp. 274-281, 1982. · Zbl 0484.68053 · doi:10.1007/BF01934440
[9] Edelsbrunner, H. and Sharir, M., The Maximum Number of Ways to Stabn Convex Nonintersecting Objects in the Plane is 2n-2,Discrete and Computational Geometry, to appear. · Zbl 0712.52009
[10] ElGindy, H. and Toussaint, G. T., Efficient Algorithms for Inserting and Deleting Edges from Triangulations,Proceedings of the International Conference on Foundations of Data Organization, Kyoto, May 22-24, 1985.
[11] Goodman, J. E. and Pollack, R., Hadwiger’s Transversal Theorem in Higher Dimensions,Journal of the American Mathematical Society, Vol. 1, to appear. · Zbl 0642.52003
[12] Hadwiger, H., Debrunner, H., and Klee, V.,Combinatorial Geometry in the Plane, Holt, Rinehart, and Winston, New York, 1964.
[13] Katchalski, M., Thin Sets and Common Transversals,Journal of Geometry, Vol. 14, pp. 103-107, 1980. · Zbl 0436.52006 · doi:10.1007/BF01918521
[14] Katchalski, M., Lewis, T., and Zaks, J., Geometric Permutations for Convex Sets,Discrete Mathematics, Vol. 54, pp. 271-284, 1985. · Zbl 0561.52002 · doi:10.1016/0012-365X(85)90111-6
[15] Preparata, F. P. and Shamos, M. I.,Computational Geometry, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[16] Wenger, R., Upper Bounds on Geometric Permutations,Discrete and Computational Geometry, to appear. · Zbl 0712.52008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.