-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
105 lines (104 loc) · 4.39 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
<!DOCTYPE html>
<HTML xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns:v="urn:schemas-microsoft-com:vml"
xmlns:xlink="http://www.w3.org/1999/xlink">
<HEAD>
<TITLE>Attractor Counterexamples</TITLE>
<STYLE>
h1, h2 { background: black; color: white; padding: 0.5ex 0.5em; margin: 0.75ex 0; }
.level { display: inline-block; width: 200px; vertical-align: middle;
padding: 0.75ex 1ex; }
.level p { margin: 0.5em; }
</STYLE>
<!--#include virtual="../analytics.html"-->
</HEAD>
<BODY>
<H2>“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</H2>
<P>
This website provides interactive demos illustrating grid orthogonal
polygons for which a magnetic <b>beacon</b>, constrained to be outside the
polygon, cannot capture a steel <b>ball</b>, 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
<a href="https://arXiv.org/abs/2006.01202">our paper</a>
(originally appearing at
<a href="http://jasonku.mit.edu/pdf/BEACON_JCDCGGG.pdf">JCDCGGG 2018</a>)
which provides the context for the problem
and proves formally that these examples are indeed unsolvable.
<H1>Attractor Counterexamples and Attempts</H1>
<a class="level" href="level1.html">
<img src="level1.svg">
<p><b>Level 1:</b> no boundary-hugging solution (but there is an external walk solution)</p>
</a>
<a class="level" href="level2.html">
<img src="level2.svg">
<p><b>Level 2:</b> no solution (any external walk)</p>
</a>
<a class="level" href="level3.html">
<img src="level3.svg">
<p><b>Level 3:</b> simpler no solution (any external walk)</p>
</a>
<a class="level" href="level4.html">
<img src="level4.svg">
<p><b>Level 4:</b> even simpler no solution (any external walk)</p>
</a>
<a class="level" href="level5.html">
<img src="level5.svg">
<p><b>Level 5:</b> oversimplified (has a solution, even boundary hugging)</p>
</a>
<a class="level" href="level6.html">
<img src="level6.svg">
<p><b>Level 6:</b> thinner version of Level 4 (no solution)</p>
</a>
<a class="level" href="level7.html">
<img src="level7.svg">
<p><b>Level 7:</b> slightly more minimal thin no solution</p>
</a>
<a class="level" href="level8.html">
<img src="level8.svg">
<p><b>Level 8:</b> reduce collinear degeneracies</p>
</a>
<!--
<UL>
<LI> <A HREF="level1.html">Level 1</A>: no boundary-hugging solution (but there is an external walk solution)
<LI> <A HREF="level2.html">Level 2</A>: no solution (any external walk)
<LI> <A HREF="level3.html">Level 3</A>: simpler no solution (any external walk)
<LI> <A HREF="level4.html">Level 4</A>: even simpler no solution (any external walk)
<LI> <A HREF="level5.html">Level 5</A>: oversimplified (has a solution, even boundary hugging)
</UL>
-->
<H1>Partial Constructions along the way</H1>
<a class="level" href="partial1.html">
<img src="partial1.svg">
<p><b>Partial 1:</b> basic notch that "locks" the ball</p>
</a>
<a class="level" href="partial2.html">
<img src="partial2.svg">
<p><b>Partial 2:</b> double notch</p>
</a>
<a class="level" href="partial3.html">
<img src="partial3.svg">
<p><b>Partial 3:</b> one spiral forces clockwise entry, blocks one boundary entry (right)</p>
</a>
<a class="level" href="partial4.html">
<img src="partial4.svg">
<p><b>Partial 4:</b> extra branch blocks both boundary entries</p>
</a>
<!--
<UL>
<LI> <A HREF="partial1.html">Partial 1</A>: basic notch that "locks" the ball
<LI> <A HREF="partial2.html">Partial 2</A>: double notch
<LI> <A HREF="partial3.html">Partial 3</A>: one spiral forces clockwise entry, blocks one boundary entry (right)
<LI> <A HREF="partial4.html">Partial 4</A>: extra branch blocks both boundary entries
</UL>
-->
<HR>
<A HREF="https://github.com/edemaine/attractor">Source code available on Github</A>
</BODY>
</HTML>