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

Simple item page
dc.creatorKaplan, Haim
dc.creatorRubin, Natan
dc.creatorSharir, Micha
dc.date2008-07-08
dc.date.accessioned2026-07-07T09:49:04Z
dc.date.available2026-07-07T09:49:04Z
dc.descriptionWe 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 $¶$ 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 $¶$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $¶$, and the case where the polyhedra of $¶$ are unbounded in a direction parallel to $\ell_0$.
dc.description10 pages+ 15 page appendix
dc.identifierhttps://arxiv.org/abs/0807.1221
dc.identifierhttp://arxiv.org/abs/0807.1221
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/164448
dc.subjectComputational Geometry
dc.titleLine Transversals of Convex Polyhedra in $\reals^3$
dc.typetext

Files

Collections

arXiv