How can a Roomba turn as little as possible? Suppose I have a convex polygon $C$ and a radius $r>0$, and I seek a path $P$ that "covers" $C$, in the sense that any point $C$ is within distance $r$ of $P$: $$d(x,P)\leq r~\forall x\in C~,$$
where $d(x,P) := \min_{x'\in P} \|x-x'\|$.   My question:  are there any analytical results (lower/upper bounds, etc.) that describe the minimum amount of turning needed to cover $P$?  The figure below shows three covering paths of a rectangle, and the upper path has a total of $9\pi$ radians worth of rotation whereas the lower two have $3\pi$.

 A: The following paper studies this "milling" problem (generalized) from a complexity viewpoint:

Arkin, E. M., Bender, M. A., Demaine, E. D., Fekete, S. P., Mitchell, J. S., & Sethia, S. (2005). Optimal covering tours with turn costs. SIAM Journal on Computing, 35(3), 531-566. (Preliminary arXiv version.)

Among many results, they prove

that the covering tour problem with turn costs is NP-complete,
  even if the objective is purely to minimize the number of turns, the pocket is
  orthogonal (rectilinear), and the cutter must move axis-parallel.

The provide several approximations algorithms for variants of the
problem. For the Roomba variant in which the orthogonal polygon
may have holes and the tour is axis-parallel, they achieve
a $3.75$-approximation ratio.

                


        
Fig.5.2.b: An optimal tour: square with square hole.

There is literature on NC milling of convex shapes, but I cannot access
any the papers, so I am not certain of their relevance:

  
*
  
*Wang, Hsu-Pin, Heng Chang, and Richard A. Wysk. "An analytical approach to optimize NC tool path planning for face milling flat convex polygonal surfaces." IIE transactions 20.3 (1988): 325-332.
  
*Prabhu, Prasad V., Anand K. Gramopadhye, and Hsu-pin Wang. "A general mathematical model for optimizing NC tool path for face milling of flat convex polygonal surfaces." The International Journal of Production Research 28.1 (1990): 101-130.
  
*Deshmukh, Abhijit V., M. M. Barash, and Hsin-Pang Wang. On selection of tool path orientations for generating prismatic features. School of Industrial Engineering, Purdue University, 1993.

