Math @ Duke

Publications [#235390] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK, On stabbling lines for convex polyhedra in 3D,
Computational Geometry, vol. 4 no. 4
(1994),
pp. 177189, ISSN 09257721
(last updated on 2018/07/17)
Abstract: 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 halfspaces 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 halfspaces as we insert or delete halfspaces dynamically. © 1994.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

