“Negative Instance for the Edge Patrolling Beacon Problem” by Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jason S. Ku, and Jayson Lynch

This website provides interactive demos illustrating grid orthogonal polygons for which a magnetic beacon, constrained to be outside the polygon, cannot capture a steel ball, which tries to move as straight as possible toward the beacon but is constrained to remain inside the polygon. You can play the levels with arrow keys, or ask the app to search for a solution via BFS. This website is a companion to our paper (originally appearing at JCDCGGG 2018) which provides the context for the problem and proves formally that these examples are indeed unsolvable.

Attractor Counterexamples and Attempts

Level 1: no boundary-hugging solution (but there is an external walk solution)

Level 2: no solution (any external walk)

Level 3: simpler no solution (any external walk)

Level 4: even simpler no solution (any external walk)

Level 5: oversimplified (has a solution, even boundary hugging)

Level 6: thinner version of Level 4 (no solution)

Level 7: slightly more minimal thin no solution

Level 8: reduce collinear degeneracies

Partial Constructions along the way

Partial 1: basic notch that "locks" the ball

Partial 2: double notch

Partial 3: one spiral forces clockwise entry, blocks one boundary entry (right)

Partial 4: extra branch blocks both boundary entries


Source code available on Github