Skip to main content
1 of 3
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Sweep-segment bot: Will this random walk sweep the plane?

This model is inspired by the random behavior of the Roomba sweeping robot.

Let a unit segment $ab$ in the plane be placed initially with $a=(0,0)$ and $b=(1,0)$. The segment is first rotated a random angle $\theta_1$ about $a$, $\theta_1 \in (-\pi,+\pi)$, sweeping out a sector of angle $\theta_1$ centered on $a$. Then it is rotated a random angle $\theta_2$ about $b$, sweeping out a sector of angle $\theta_2$ centered on $b$. Odd steps rotate about $a$, even about $b$, each with $\theta_i \in (-\pi,+\pi)$; each sector sweeps $< \pi$.

An example is shown below. The first, darker sector sweeps $\theta_1=114^\circ$ (ccw), the second sweeps $\theta_2=-140^\circ$ (cw), and the sequence continues $$\theta_3,\ldots = 104^\circ,-112^\circ,-93^\circ,-156^\circ,15^\circ,-97^\circ,-37^\circ,72^\circ \;.$$
r10 http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10.jpg

Does the described random walk of this segment eventually sweep every point of the plane with probability 1? That is, will the union of the sectors cover the plane?

My guess is: 'Yes,' because of the analogy with Pólya's recurrence theorem for random walks on a 2D lattice. Indeed if the random angle is discretized to $\theta_i \in \{ -\pi, -\pi/2, +\pi/2, +\pi \}$, then the segment midpoint executes a random walk on a lattice. On the other hand, it seems remarkable that this process would actually sweep the whole plane. Here is the same example extended to 10,000 steps:
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/SweepBotR1N10k.jpg
Despite the similarities, I don't see how to directly reduce this model to a conventional random walk to answer the posed question. If anyone does, I would appreciate suggestions. Even just your intuitions are welcomed. Thanks!

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958