ε-Guarantee of a covering of 2D domains using random-looking curves

- An algorithm for covering a 2D domain with a random-looking curve is proposed.
- Precise bounds on the covering distance are guaranteed via algebraic formulation.
- The set of precise local extrema of distances from a curve is computed.
- The set of local extrema is used to iteratively construct the covering curve.

The problem of covering a given 2D convex domain D with a C1 random-looking curve C is considered. C within D is said to cover D up to ϵ > 0 if all points of D are within ϵ distance of C. This problem has applications, for example, in manufacturing, 3D printing, automated spray-painting, polishing, and also in devising a (pseudo) random patrol-path that will visit (i.e. cover) all of D using a sensor of ϵ distance span. Our distance bound approach enumerates the complete set of local distance extrema, enumeration that is used to provide a tight bound on the covering distance. This involves computing bi/tri-normals, or circles tangent to C at two/three different points, etc. A constructive algorithm is then proposed to iteratively refine and modify C until C covers a given convex domain D and examples are given to illustrate the effectiveness of our algorithm.

315Iterative construction of covering curve, shown in black, for the quadrilateral domain, whose boundary is shown in blue. The distance local extrema are indicated as centers of circles shown in red.