Polygon-Constrained Motion Planning Problems

We consider the following class of polygon-constrained motion planning problems: Given a set ofkcentrally controlled mobile agents (saypebbles) initially sitting on the vertices of ann-vertex simple polygonP, we study how to plan their vertex-to-vertex motion in order to reach with a minimum (eithermaximumortotal) movement (either in terms ofnumber of hopsorEuclidean distance) a final placement enjoying a given requirement. In particular, we focus on final configurations aim-ing at establishing some sort of visual connectivity among the pebbles, which in turn allows for wireless and optical intercommunication. There-fore, after analyzing the notable (and computationally tractable) case of gathering the pebbles at asingle vertex (i.e., the so-calledrendez-vous), we face the problems induced by the requirement that pebbles have eventually to be placed at: (i) a set of vertices that form aconnected subgraph of thevisibility graphinduced by P,sayG(P)(connectivity), and (ii) a set of vertices that form acliqueofG(P)(clique-connectivity). We will show that these two problems are actually hard to approxi-mate, even for the seemingly simpler case in which the hop distance is considered.