Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235390] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK, On stabbling lines for convex polyhedra in 3D, Computational Geometry, vol. 4 no. 4 (1994), pp. 177-189, ISSN 0925-7721
    (last updated on 2018/10/21)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320