×

Line transversals of convex polyhedra in \(\mathbb{R}^3\). (English) Zbl 1211.52010

Summary: We establish a bound of \(O(n^2k^{1+\varepsilon})\), for any \(\varepsilon>0\), on the combinatorial complexity of the set \(\mathcal{T}\) of line transversals of a collection \(\mathcal{P}\) of \(k\) convex polyhedra in \(\mathbb{R}^3\) with a total of \(n\) facets, and we present a randomized algorithm which computes the boundary of \(\mathcal{T}\) in comparable expected time. Thus, when \(k\ll n\), the new bounds on the complexity (and construction cost) of \(\mathcal{T}\) improve upon the previously best known bounds, which are nearly cubic in \(n\). To obtain the above result, we study the set \(\mathcal{T}_{\ell_0}\) of line transversals which emanate from a fixed line \(\ell_0\), establish an almost tight bound of \(O(nk^{1+\varepsilon})\) on the complexity of \(\mathcal{T}_{\ell_0}\), and provide a randomized algorithm which computes \(\mathcal{T}_{\ell_0}\) in comparable expected time. Slightly improved combinatorial bounds for the complexity of \(\mathcal{T}_{\ell_0}\) and comparable improvements in the cost of constructing this set are established for two special cases, both assuming that the polyhedra of \(\mathcal{P}\) are pairwise disjoint: the case where \(\ell_0\) is disjoint from the polyhedra of \(\mathcal{P}\), and the case where the polyhedra of \(\mathcal{P}\) are unbounded in a direction parallel to \(\ell_0\). Our result is related to the problem of bounding the number of geometric permutations of a collection \(\mathcal{C}\) of \(k\) pairwise-disjoint convex sets in \(\mathbb{R}^3\), namely, the number of distinct orders in which the line transversals of \(\mathcal{C}\) visit its members. We obtain a new partial result on this problem.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B10 Three-dimensional polytopes
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52C45 Combinatorial complexity of geometric structures
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI