On Lines Missing Polyhedral Sets in 3-Space

We show some combinatorial and algorithmic results concerning sets of lines and polyhedral objects in 3-space. Our main results include:(1) An O((n^3)2^(c?log n)) upper bound on the worst case complexity of the set of lines missing a star-shaped compact polyhedron with n edges, where c is a suitable constant.(2) An O((n^3) 2^{c?log n}) upper bound on the worst case complexity of the set of lines that can be moved to infinity without intersecting a set of n given lines, where c is a suitable constant. This bound is almost tight.(3) An O(n^{1.5+?}) randomized expected time algorithm that tests whether a direction v exists along which a set of n red lines can be translated away from a set of n blue lines without collisions.(4) Computing the intersection of two polyhedral terrains in 3-space with n total edges in time O(n^{4/3+?} + k^{1/3}n^{1+?} + klog^2 n), where k is the size of the output, and epsilon >0 an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelle at al.The tools used to obtain these results include Plucker coordinates of lines, random sampling and polarity transformations in 3-space.A preliminary version of this work appeared in the Proceedings of the 9th ACM Symposium on Computational Geometry.

ICSI Technical Report TR-93-034

Technical Report