On stabbling lines for convex polyhedra in 3D
Published
Journal Article
A line ℓ is called a stabbling line for a set Bof convex polyhedra in R3 if it intersects every polyhedron of B. This paper presents an upper bound of O(n3log n) on the complexity of the space of stabbling lines for B, where n is the number of edges in the polyhedra of B. We solve a more general problem that counts the number of faces in a set of convex polyhedra, which are implicitly defined by a set of half-spaces and a set of hyperplanes. We show that the former problem is a special case of the latter problem. We also apply this technique to obtain an upper bound on the number of distinct faces that ever appear on the intersection of a set of half-spaces as we insert or delete half-spaces dynamically. © 1994.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK
Published Date
- January 1, 1994
Published In
Volume / Issue
- 4 / 4
Start / End Page
- 177 - 189
International Standard Serial Number (ISSN)
- 0925-7721
Digital Object Identifier (DOI)
- 10.1016/0925-7721(94)90016-7
Citation Source
- Scopus