On stabbling lines for convex polyhedra in 3D


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