Recently, Guibas et al. [7] studied deformable necklaces - flexible chains of balls, called beads, in which only adjacent balls can intersect. In this paper, we investigate a problem of covering a necklace by cylinders. We consider several problems under different optimization criteria. We show that optimal cylindrical cover of a necklace with n beads in R~3 by k cylinders can be computed in polynomial time. We also study a bounding volume hierarchy based on cylinders.
展开▼