caa a22 4500 469075074 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920801xx s 000 0 eng 10.1007/BF02293043 doi (NATIONALLICENCE)springer-10.1007/BF02293043 Finding stabbing lines in 3-space [Elektronische Daten] [M. Pellegrini, P. Shor] 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 % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVy0df9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lqpe0x% c9q8qqaqFn0dXdir-xcvk9pIe9q8qqaq-xir-f0-yqaqVeLsFr0-vr% 0-vr0xc8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaWGpbGaai% ikaiaad6gadaahaaWcbeqaaiaaiodaaaGccaaIYaWaaWbaaSqabeaa% caWGJbWaaOaaaeaaciGGSbGaai4BaiaacEgacaWGUbaameqaaaaaki% aacMcaaaa!4368! $$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. Springer-Verlag New York Inc., 1992 Pellegrini M. Courant Institute, New York University, 251 Mercer Street, 10012, New York, NY, USA aut Shor P. AT&T Bell Laboratories, 2D-149, 600 Mountain Avenue, 07974, Murray Hill, NJ, USA aut Discrete & Computational Geometry Springer New York 8/2(1992-08-01), 191-208 0179-5376 8:2<191 1992 8 454 https://doi.org/10.1007/BF02293043 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293043 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Pellegrini M. Courant Institute, New York University, 251 Mercer Street, 10012, New York, NY, USA aut NATIONALLICENCE 700 1- Shor P. AT&T Bell Laboratories, 2D-149, 600 Mountain Avenue, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/2(1992-08-01), 191-208 0179-5376 8:2<191 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer