Translational Covering of Closed Planar Cubic B-Spline Curves

Abstract

Spline curves are useful in a variety of geometric modeling and graphics applications and covering problems abound in practical settings. This work defines a class of covering decision problems for shapes bounded by spline curves. As a first step in addressing these problems, this paper treats translational spline covering for planar, uniform, cubic B-splines. Inner and outer polygonal approximations to the spline regions are generated using enclosures that are inside two different types of piecewise-linear envelopes. Our recent polygonal covering technique is then applied to seek translations of the covering shapes that allow them to fully cover the target shape. A feasible solution to the polygonal instance provides a feasible solution to the spline instance. We use our recent proof that 2D translational polygonal covering is NP-hard to establish NP-hardness of our planar translational spline covering problem. Our polygonal approximation strategy creates approximations that are tight, yet the number of vertices is only a linear function of the number of control points. Using recent results on B-spline curve envelopes, we bound the distance from the spline curve to its approximation. We balance the two competing objectives of tightness vs. number of points in the approximation, which is crucial given the NP-hardness of the spline problem. Examples of the results of our spline covering work are provided for instances containing as many as six covering shapes, including both convex and nonconvex regions. Our implementation uses the LEDA and CGAL C++ libraries of geometric data structures and algorithms.