Decontaminating planar regions by sweeping with barrier curves
Borislav Karaivanov, Minko Markov, Jack Scott Snoeyink, Tzvetalin S. Vassilev · 2014
\If seven maids with seven mops Swept it for half a year. Do you suppose, the Walrus said, \That they could get it clear? \I doubt it, said the Carpenter, And shed a bitter tear. We consider the problem of decontaminating (cleaning) the interior of a planar shape by sweeping it with barrier curves. The contaminant is assumed to instantly travel any path not blocked by a barrier. We show that any decontamination sweep can be converted to one that uses only line segment barriers without increasing length. We dene the sweepwidth of a region as the minimum over all decontamination sweeps of the maximum over time of barrier length used, and determine sweepwidth for some simple classes of orthogonal polygons. However, we also show that computing sweepwidth in general, even for orthogonal polygons, isNP-hard.