CYLINDRICAL HIERARCHY FOR DEFORMING NECKLACES
Sergey Bereg · International Journal of Computational Geometry & Applications · 2004
Recently, Guibas et al.10 studied deformable necklaces — flexible chains of balls, called beads, in which only adjacent balls can intersect. In this paper, we investigate the 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 ℝ3 by k cylinders can be computed in polynomial time. We also study a bounding volume hierarchy based on cylinders.