9
$\begingroup$

Imagine sheep fill a simple (simply connected) polygon $P$, except at one vertex $x$ there is no sheep. One convex vertex $g$ of $P$ is a gate through which the sheep should pass. A herding dog sits at a vertex $x$ and barks. Every sheep point $s$ moves along a radial line from $x$, until $s$ hits the boundary $\partial P$. Then, if the forward vector $v$ from $s$ along $\partial P$ has a strictly positive projection on the vector $xs$, then $s$ moves forward along $v$. If the projection is zero or negative, $s$ is stuck.

The example below shows a polygon $P$ that is not entirely cleared from $x$, because the ray $xa$ is orthogonal to the edge $e$ incident to $g$, and the sheep above that ray are all stuck. (The barking penetrates the fence $\partial P$.) So we could say that $P,g$ is not $1$-herdable from $x$.


          Sheep
However, after the sheep have been cleared from $x$, the dog can walk along the cleared boundary to $x'$, which then clears the remaining sheep because the angle formed by $x' b$ with $e$ is obtuse. So we could say $P,g$ is $2$-herdable from $x$.

I am interested in characterizing the shapes of $P$ that are herdable from some $x$, $k$-herdable for any $k$. For $k=1$, it seems this is necessary and sufficient: $P,g$ is $1$-herdable from $x$ if there is no point $p$ on an edge $e$ such that: (a) $e$ faces $x$, (b) the angle $xp$ makes with $e$ is $\ge 90^\circ$ away from $g$. I realize this formulation is not precise, but perhaps it is clear from the figures.

I would be interested in any description of the shapes of polygons that are $1$- or $2$- or $k$-herdable, and shapes that are definitely not so herdable. For example: All convex polygons with all obtuse angles are $1$-herdable with appropriate choice of $x$ with respect to $g$. But a square is not herdable for any $k$: Some sheep gets stuck in a corner, and the dog cannot occupy the same point as that stuck sheep. (I make an exception for the initial dog vertex $x$.)

Q. Which shapes are, and which shapes are not herdable for any $k$, for any placement of $g$ and $x$?

It is likely too much to hope for a complete characterization, but perhaps large classes of polygon shapes can be settled, for specific $k$.


This notion of herding by repulsion from $x$ is in a sense the inverse of the concept of beacon routing, which relies on attraction. Here is one source among many on that topic:

Shermer, Thomas C. "A combinatorial bound for beacon-based routing in orthogonal polygons." arXiv:1507.03509 (2015).

$\endgroup$
12
  • $\begingroup$ Do you insist on one gate g? You might show every polygon is herdible through two gates that are (say) separated by at most one vertex. This extension might shed light on your classification. Gerhard "These Ways To The Egress" Paseman, 2017.09.28. $\endgroup$ Sep 28, 2017 at 18:28
  • $\begingroup$ Also, make sure your field is not fractal. I suspect members of (iterations toward ) the Koch snowflake are not k herdible for small k. Gerhard "Worse Than An Art Gallery" Paseman, 2017.09.28. $\endgroup$ Sep 28, 2017 at 18:32
  • $\begingroup$ @GerhardPaseman: Any assumption that leads to clarity is welcome. I wanted to remove dynamics. So I assume the dog sits at a vertex and clears a region. Then moves to another and clears. And so on. $\endgroup$ Sep 28, 2017 at 18:47
  • 1
    $\begingroup$ If a sheep is in x, then it seems there is an indeterminacy of the direction of motion. We can assume they are never in x, but they may arrive at a sharp corner, and the only way to herd them out of that corner is to move the dog there, so we run again into this indeterminacy. Maybe assume the choice is random? Another indeterminacy happens if the gate angle is >90 and x is adjacent to it: will the sheep choose the gate, or it will move along the next edge? Maybe assume it always chooses the gate. A simple example containing both these cases is a triangle with obtuse gate. $\endgroup$ Sep 29, 2017 at 9:25
  • 1
    $\begingroup$ Another analytic approach would be to have the herding point x outside the polygon (use a really big dog), and consider when herding is successful as x approaches the polygon. It may have to do with when " parts of the convex hull are strictly contained with the polygon ", more accurately when all obtuse lines to a polygon boundary stay outside the polygon. Gerhard "Is Trying To Be Acute" Paseman, 2017.09.29. $\endgroup$ Sep 29, 2017 at 14:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.