10
$\begingroup$

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$.

Three covering paths

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You may want to take a look at the Planning Algorithms book, especially section 7.6 on coverage planning. $\endgroup$
    – Rodrigo de Azevedo
    Commented Jan 31, 2017 at 18:49
  • 1
    $\begingroup$ The greedy algorithm is: go as far as you can in uncovered area without turning, then turn to follow the boundary of the uncovered area. This leads to the last path. Does every polygon have some greedy path which is optimal? $\endgroup$
    – user44143
    Commented Jan 31, 2017 at 21:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

                Milling
        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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I would expect the complexity to come from the holes, but the question asked about convex polygons. $\endgroup$
    – user44143
    Commented Feb 1, 2017 at 0:37
  • 1
    $\begingroup$ @MattF.: Yes, or perhaps from non-convexity (even without holes). $\endgroup$
    – Joseph O'Rourke
    Commented Feb 1, 2017 at 13:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .