Sweeping a Domain with Line-Of-Sight Between Covisible Agents

We first consider the SweepWithNoReturn version where the agents do not have to return to the depot $s$ (so we are minimizing the time when the last point of $P$ is swept). We then show how to modify the reduction to prove hardness of the SweepWithReturn version in which the agents must return to $s$ (and the time of the return defines the makespan). Given an instance of 3-Partition (Can given integers $x_1\mathrm{\dots }{x}_{3m}$ be partitioned into $m$ triples with equal sums?), we construct a polygon $P$ with $O(m)$ vertices, as shown in Figure 2, consisting of a tall and very narrow rectangular room (whose width is exaggerated in the figure, to show details) with a staircase on the right and with two corridors (each of which has length $50mS$) extending from the room as shown. The height of the room is $mS$ where $S=\sum x_i/m$ is the target sum in each of the sought triples of the given numbers; the width, $\delta$, is very small (e.g., ).

The corridors ending with $s$ and $t$ are very thin and long ($50mS$). Thus, in any optimal sweeping schedule each of the corridors is swept exactly once: the sweep starts at $s$ (by definition) and ends with one of the agents at $t$ (recall that for now we do not restrict where the agents are at the conclusion of the sweep). The top of the room has a chimney for each number in the set. The chimneys are very narrow (width ) and chimney $i$ has height $x_i/2$. Finally, the height of each step in the staircase is $S$.

If the 3-Partition instance is feasible, then $P$ can be swept as follows (with both $a$ and $b$ moving at the maximum, unit speed, and the segment $ab$ staying vertical throughout the motion): the top agent $a$ will visit and ascend chimneys corresponding to triples in the solution. While $a$ is in chimney $i$ (either ascending or descending), the bottom agent $b$ moves down by $x_i$. After $a$ finishes a triple that sums to $S$, $b$ has moved down by $S$. (Note that apart from the duration during which the segment sweeps the horizontal corridor, horizontal movements are not particularly relevant for the analysis, since the room is so narrow, and chimneys are even narrower, implying that the sweep segment must be nearly vertical at all times.) Finally, in this first pass, $ab$ moves all the way to the right, arriving with length $S$ so that it is just long enough to sweep the top step of the staircase (including $v_1$) without spending further time having agents move vertically. See the left of Figure 2 for an example of this motion to sweep the first step. Next, $ab$ will move to the left of the polygon and sweep more chimneys before moving back to the right to sweep $v_2$ (Figure 2, right). Such sideways sweeps are repeated until all $m$ of the stairs are swept. (Again, all horizontal motion of agents is not relevant to the overall makespan, since $m$ left-to-right motions are still much less than length 1.) The time to sweep the room, along with the staircases, is at most $mS+2m\delta$. The total time to sweep everything is $101mS+2m\delta$.

Conversely, suppose the stairs are swept in any other way, then either $b$ has to wait for at least a duration of 1 before aligning with a stair tread, or $a$ has to waste time by not going into a chimney with a single up-and-down pass. The first case occurs when the agents pick a triplet of chimneys ($x,x^{\prime },x^{\prime \prime }$) with a sum larger than $S$, then agent $a$ still needs to trace the boundary of the chosen chimneys to sweep them completely. Even if $b$ can already reach the depth of the next staircase vertex (say, $v_j$), it must still wait for $a$ to finish sweeping the last chimney in the triplet so that it can finally move to sweep $v_j$, which takes longer than $S$. In the second case, the chosen triplet of chimneys has a sum smaller than $S$. In this case, agent $a$ will have to wait for agent $b$ to reach the depth of the next staircase vertex. This still costs the agents a time of $S$ while leaving taller chimneys for other triplets (which leads back to the previous case). Note that there is no reward for $a$ to partially sweep a chimney, since $a$ must exit the chimney and align vertically with $b$ when $b$ touches $v_j$ so that the both of them can sweep the vertical edge incident to $v_j$. Agent $b$ can technically move diagonally downward to save time, but in that case, the most it can save is $\delta$, which is chosen to be much smaller than $1/m^{10}$ (so in total it can save at most $m\cdot 1/m^{10}=1/m^9\ll 1$).

We now modify the above gadget to show the hardness of our SweepWithReturn version. See Appendix A for the modified gadget. As in the proof for the version without return to $s$, the segment will sweep the top chimneys (solving the 3-Partition) and sweep the convex vertices on the right in parallel. Once the segment is done with the right convex vertices and the top chimneys, the segment sweeps the inverted chimneys (also solving the same 3-Partition instance); each time it sweeps 3 bottom chimneys that make a sum $S$, the segment will retract itself (top endpoint moving down) so that it could reach the convex vertices on the left ($v_1^{\prime },v_2^{\prime },\mathrm{\dots }$). The overall makespan will then be $3mS+O(\delta )$. As in the reduction for the version without return to $s$, any deviation from the described schedule incurs a wait of at least 1 by at least one of the agents. $◀$

By Lemma 2, the union of paths for $a$ and $b$ visits all convex vertices; thus, the union is at least as long as any path within $P$ visiting all convex vertices, implying that the union cannot be shorter than $\frac{1}{2}|\partial P|$. This is because in a simple polygon, $\partial P$ is the shortest tour that visits all convex vertices, and any path that does so must be at least half as long. $◀$

Our algorithm partitions the polygon into subpolygons, each of which has a simple sweeping strategy. The dual of the partition is a tree, which allows the line segment to sweep all the subpolygons, traversing the tree recursively.

The details of the partition are as follows. Consider any edge $e=w_1{w}_2$ of the polygon. We first compute the histogram polygon with base $e$, $HP(e)$, which is defined to be the union of all interior chords perpendicular to $e$ and having an endpoint on $e$ (a chord is a line segment connecting two points of $\partial P$ and stays completely within $P$). Let $(w_1,w_1^{\prime })$ be such a chord anchored at $w_1$. We then compute the visibility polygon of $w_1$ restricted to points that are left of $(w_1,w_1^{\prime })$; call the polygon $VP(w_1)$. Similarly, we compute another visibility polygon to the right of $(w_2,w_2^{\prime })$, called $VP(w_2)$. Then, $P(e)=HP(e)\cup VP(w_1)\cup VP(w_2)$ is one subpolygon in our partitioning scheme. See Figure 3 for an example of $P(e)$. Notice that the boundary of $P(e)$ includes some new “shadow chords,” each of which becomes a histogram base for subsequent subpolygons in the partition. We will order these chords counterclockwise. The process is complete when every shadow chord that has been generated has been utilized as a histogram base for a subpolygon adjacent to the subpolygon that generated the shadow chord. For the first subpolygon, we will simply use the visibility polygon of $s$. The overall partitioning of $P$ can be done in linear time, utilizing a triangulation of $P$ (similar to computing window partition trees [35] for link distances in simple polygons).

We now describe the recursive process to sweep a subpolygon $P(e)$ and its descendants, for an edge $e=w_1{w}_2$ of $P$ (refer to Figure 3). The agents start at the endpoint $w_1$ of $e$; once the process is completed, i.e. when the segment finishes sweeping $P(e)$ and its descendants, both agents return to $w_1$. First, $a$ sits at $w_1$ while $b$ travels clockwise around the boundary of $VP(w_1)$ until reaching $w_1^{\prime }$; this way the rotating segment $ab$ sweeps $VP(w_1)$. Next, $HP(e)$ is swept by the segment perpendicular to $e$: $b$ travels along the top polygonal path of the histogram while $a$ moves along $e$ ($a$ slows itself in order that $ab$ remains perpendicular to $e$). Then, the segment rotates clockwise around $w_2$ to sweep $VP(w_2)$; at this point $P(e)$ is completely swept and the segment will move to the furthest (w.r.t. $w_2$) endpoint of the first “shadow chord” (see $e_1$ in Figure 3). After the segment completely sweeps $P(e_1)$ (and its descendants), it will move to the next child of $P(e)$. This will be repeated until all descendants of $P(e)$ are swept. Notice that while sweeping the children, the segment will at times move counterclockwise along the boundary of $P(e)$. Once the segment is done with all children of $P(e)$, both of its endpoints will regroup at $w_1$.

We will first perform analysis on any subpolygon $P(e)$ other than the root. Without loss of generality, we assume that the segment always starts sweeping from the left vertex of $e$ (i.e., $w_1$ in the figure). First, the endpoints sweep $P(e)$ by traveling from $w_1$ to $w_2$, this will incur a cost of $|\partial P(e)|-|e|$. This is because $a$ will move along $e$ with a speed at most that of $b$. Second, the endpoints travel counterclockwise to visit all children of $P(e)$. The cost of this counterclockwise traversal is at most $|\partial P(e)|-|e|$. Overall, the cost of sweeping $P(e)$ and moving counterclockwise to visit all of its children is

where $\partial P(e)\cap \partial P$ are the portions of $\partial P(e)$ that belong to the boundary of $P$, and $C(e)$ are the base edges of children of $P(e)$. For the root subpolygon $P(s)$, the cost to sweep it and visit all of its children is at most

Here, $C(s)$ is the set of all chords generated and associated with $P(s)$.

Let $E$ be the set of all additional chords created during the partition process. The total cost to sweep $P$ will be the sum of the two terms above:

We have $|e|\le |\partial P(e)\cap \partial P|$ for each $e\in E$ because $\partial HP(e)\cap \partial P\subseteq \partial P(e)\cap \partial P$ is an orthogonal projection of $e$ onto $\partial P$. Thus overall, the sweeping cost of $P$ is at most

The first inequality holds because the portions of each $P(e)$ that belong to $\partial P$, i.e. $\partial P(e)\cap \partial P$, are pairwise disjoint for different $e\in E$. Thus, ${\sum }_{e\in E}|\partial P(e)\cap \partial P|+|\partial P(s)\cap \partial P|=|\partial P|$. The second inequality follows directly from Lemma 3. $◀$

By definition of $F_i$, both endpoints of $ab$ never enter the interior of $F_i$ and $R_i$; which means the interior of $R_i$ must be swept by interior points of $ab$. Since the beginning of the schedule, $a$ and $b$ are both at $s$ so they are outside of $R_i$ (the intersection between the segment $ab$ and the interior of $R_i$ is empty). Consider the moment when some interior points of $ab$ enter $R_i$ (Figure 6): the segment is either aligned with an edge of the hull or touches a convex vertex $x_1$ of the hull. If $ab$ is supported by a (necessarily reflex) vertex of $P$, then the segment will start intersecting the exterior of $P$ as it moves. In order to not intersect with the exterior, the vertex $x_1$ must be supported by a reflex vertex of $F_i$, which may only happen if there is another (reflex) vertex $x_2$ of the hull collocated with $x_1$. This is due to the fact that any convex vertex of a GCH is either a vertex of $P$, or is supported by $F_i$ padded by another (reflex) vertex. Therefore, $R_i$ must collapse at some vertex. $◀$

Now we have the following result based on the fact that $R_i$ has to collapse:

Note that by definition, a pocket must contain at least one obstacle. Let $\mathscr{H}$ be the set of obstacles in $R_i$, and let $\rho$ be the only pocket that $R_i$ has, then $\rho$ contains all obstacles in $\mathscr{H}$. Consider the PSLG created by walking along $\partial R_i$ counterclockwise: since $R_i$ collapses onto itself at some vertices, it will create more than one cycle in this graph. However, only one cycle (the one bounding $\rho$) has any obstacle in it, therefore the rest of the cycles in the PSLG are degenerate and empty. But if the PSLG contains all of these degenerate cycles, it means that $R_i$ was not an actual GCH of the obstacles, since we can get rid of all of these degenerate cycles and only keep $\rho$ to get a smaller set that contains all obstacles, which is a contradiction. Therefore, $\rho$ cannot be the only pocket. $◀$

Note that the above lemmas only state that $R_i$ will collapse and create at least two pockets, each having at least one obstacle. Now, for each pocket $\rho$ in $R_i$, we can reapply the same arguments: let $R_{\rho }$ be the GCH containing all obstacles in $\rho$ then $R_{\rho }$ must also collapse onto itself somewhere, and create at least two pockets each containing some obstacles. We can keep repeating the same process and each time a GCH collapses it splits the set of obstacles into at least two subsets, each subset belonging to a unique pocket. Since there are a finite amount of obstacles, after a finite amount of these collapsing and splitting steps, each obstacle will be contained in its own pocket (not necessarily a pocket of the first GCH $R_i$):

Next, we obtain the following upper bound on the total perimeter of the pockets:

To prove this, we define a tree structure where each node is either a GCH or a pocket. We call $R_i$ the root GCH, and the pockets resulted from the collapsing of $R_i$ its child pockets. For each pocket, we call the GCH containing all of its obstacles its child GCH. Similarly, each child GCH also has its child pockets. Note that a GCH node could have multiple children (pockets) but a pocket can only have one child. In this tree, only pocket nodes can be leaf nodes. A leaf pocket node is one in which there is exactly one obstacle in it. We use $child(\cdot )$ to denote the set of children of a node. For any GCH node $R$, we have the inequality

This is because each pocket is a different part of $R$ (two pockets share at most one vertex in $R$), therefore their total perimeter must be less than $|\partial R|$. Next, for any pocket node:

This is because $child(\rho )$ is a GCH in $\rho$ therefore its perimeter cannot be larger than $|\partial \rho |$. The tree we have now is one such that the perimeter of each node is greater than or equal to the total perimeter of its children, therefore we can conclude that the perimeter of any GCH node is greater than or equal to the total perimeter of all of its descendant leaf pocket nodes. This applies to the root GCH $R_i$ as well, which proves the lemma. $◀$

We finally prove the lower bound for the approximation algorithm:

(Recall that $MS{T}^{\ast }$ is the minimum spanning tree with Steiner points that spans all holes and the outer boundary of $P$.)

Let ${\mathrm{\Phi }}_i$ be the set of pockets where each pocket contains exactly one obstacle in $F_i$. If an obstacle $H$ is a convex hole and $\rho$ is its pocket, then $|\partial H|\le |\partial \rho |$. However, if $H$ is a reflex chain, then $2|\partial H|\le |\partial \rho |$: this is because the perimeter of the GCH $R$ of $H$ in $\rho$ is twice longer than $\partial H$ (a GCH of a reflex chain is simply the chain traversed back and forth). We will denote ${\mathscr{H}}_h$ (resp. ${\mathscr{H}}_r$) as the set of convex hole (resp. reflex chain) obstacles in $F_i$. We acquire the following using Lemma 9:

Let ${\pi }_i={\pi }^{\ast }\cap \partial F_i$ (the portion of ${\pi }^{\ast }$ in $\partial F_i$), then by definition $\partial F_i={\pi }_i\cup ({\bigcup }_{H\in {\mathscr{H}}_r}\partial H)$ so $|\partial F_i|=|{\pi }_i|+{\sum }_{H\in {\mathscr{H}}_r}|\partial H|$. Using the above inequality we obtain:

Summing over all $F_i$, we achieve the first lower bound of the lemma:

Note that $|\partial P|\le 2|{\pi }^{\ast }|$ because any portion of ${\pi }^{\ast }$ is counted twice during the sum: any edge of ${\pi }^{\ast }$ is shared by at most two different faces.

To prove the second bound in the lemma, we introduce a way to connect all of the convex holes to their respective $\partial F_i$ such that the total cost of these connections is bounded by $O(|{\pi }^{\ast }|)$. These connections, along with ${\pi }^{\ast }$​, will serve as a network connecting all components of the boundary of $P$, and the total length of this network cannot be shorter than the length of $MS{T}^{\ast }$ (the minimum Steiner tree connecting these components), which will give us the second bound of the lemma. We only consider convex holes in this case because any reflex chain obstacle is already connected to ${\pi }^{\ast }$ by definition.

Recall that when $R_i$ collapses (and creates pockets), there will be at least one collapsing vertex which is supported by a reflex vertex of either $\partial P$ or ${\pi }^{\ast }$. Let $x$ be any collapsing vertex that belongs to pocket $\rho$ and $H$ be the convex hole in $\rho$, and let ${\pi }_{\rho }$ be the (geodesic) shortest path from $H$ to $x$ (see Figure 4 for an illustration). ${\pi }_{\rho }$ is the shortest path between a point $u\in \partial H$ and $x$. We note that $u$ is the only point shared between ${\pi }_{\rho }$ and $\partial H$ because if there is another point $w\in {\pi }_{\rho }\cap \partial H$ then ${\pi }_{\rho }$ is suboptimal (we can simply remove the subpath from $u$ to $w$ to get a better path). Therefore, if we remove $H$ from $\rho$ and compute the shortest path between $u$ and $x_{\rho }$ it will stay the same. Since ${\pi }_{\rho }$ is the shortest path between two points in a simple polygon ($\rho$ without $H$), it cannot be longer than a half of $\partial \rho$:

Let ${\mathrm{\Phi }}_h$ (resp. ${\mathrm{\Phi }}_r$) be the set of all pockets of the convex holes (resp. reflex chains) in $F_i$. Note that ${\mathrm{\Phi }}_h\cup {\mathrm{\Phi }}_r={\mathrm{\Phi }}_i$ and ${\mathrm{\Phi }}_h\cap {\mathrm{\Phi }}_r=\mathrm{\varnothing }$. Using (1) and (2):

Recall that for each pocket of a reflex chain obstacle, the perimeter of the pocket is at least double that of the reflex chain so $2{\sum }_{H\in {\mathscr{H}}_r}|\partial H|\le {\sum }_{\rho \in {\mathrm{\Phi }}_r}|\partial \rho |$, therefore:

Let $\mathrm{\Phi }$ be the set of all pockets containing convex holes of every face, by summing the above inequality over all $F_i$ we obtain ${\sum }_{\rho \in \mathrm{\Phi }}|{\pi }_{\rho }|\le |{\pi }^{\ast }|.$ Finally, the length of the network connecting all boundary components, i.e. the union ${\pi }^{\ast }\cup ({\bigcup }_{\rho \in \mathrm{\Phi }}{\pi }_{\rho })$, is $L={\sum }_{\rho \in \mathrm{\Phi }}|{\pi }_{\rho }|+|{\pi }^{\ast }|\le 2|{\pi }^{\ast }|$. Since $L$ cannot be shorter than $MS{T}^{\ast }$:

$◀$

With the above lemma, the perimeter of the degenerate polygon $P^{\prime }$ is $|\partial P^{\prime }|\le (12+ϵ)\cdot OPT$ for any $ϵ>0$ (note that we need to double $MS{T}^{\ast }$ to create $P^{\prime }$), assuming we are using a PTAS to compute the minimum Steiner tree connecting all boundaries of $P$. Based on Lemma 4, the schedule computed on $P^{\prime }$ using the approximation algorithm in Theorem 5 would yield a makespan within $4|\partial P^{\prime }|\le (48+4ϵ)\cdot OPT$. Thus, we obtain the theorem: