Line Transversals of Convex Polyhedra in $\reals^3$

Details Line Transversals of Convex Polyhedra in $\reals^3$ Line Transversals of Convex Polyhedra in $\reals^3$

2008-07-08

arxiv.org/abs/0807.1221v1

Computer Science

Computational Geometry

10 pages+ 15 page appendix

Scientific paper

We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a total of $n$ facets, and present a randomized algorithm which computes the boundary of $\T$ in comparable expected time. Thus, when $k\ll n$, the new bounds on the complexity (and construction cost) of $\T$ improve upon the previously best known bounds, which are nearly cubic in $n$. To obtain the above result, we study the set $\TL$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\eps})$ on the complexity of $\TL$, and provide a randomized algorithm which computes $\TL$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\TL$, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of $\P$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $\P$, and the case where the polyhedra of $\P$ are unbounded in a direction parallel to $\ell_0$.

Affiliated with

Also associated with

No associations

Rating

Line Transversals of Convex Polyhedra in $\reals^3$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Line Transversals of Convex Polyhedra in $\reals^3$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Line Transversals of Convex Polyhedra in $\reals^3$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-268684