2d:null 2e:["$","title",null,{"children":"Sperner’s Lemma | Vinícius Mello | Observable"}] 33:Tb43,{ const w = Math.min(width, 400); const context = DOM.context2d(w, 0.85 * w); const vs = [ [w / 2, 10], [10, 0.85 * w - 10], [w - 10, 0.85 * w - 10] ]; const point = (bary, vss = vs) => { let p = [0, 0]; for (let i = 0; i < 3; ++i) { p[0] += vss[i][0] * bary[i]; p[1] += vss[i][1] * bary[i]; } return p; }; const op = (a, b) => { let r; if (a == 0 && b == 1) return 2; if (a == 1 && b == 0) return 2; if (a == 0 && b == 2) return 1; if (a == 2 && b == 0) return 1; if (a == 1 && b == 2) return 0; if (a == 2 && b == 1) return 0; }; const cs = ["Tomato", "DarkSeaGreen", "DarkSlateBlue"]; context.lineWidth = 2; for (const t of triangle) { const a = [vertex.color[t[0]], vertex.color[t[1]], vertex.color[t[2]]]; const sgn = permsgn(a); const p0 = point(vertex.bary[t[0]]); const p1 = point(vertex.bary[t[1]]); const p2 = point(vertex.bary[t[2]]); const ps = [p0, p1, p2]; for (let i = 0; i < 3; ++i) { ps[i][0] = (1 - time) * ps[i][0] + time * vs[a[i]][0]; ps[i][1] = (1 - time) * ps[i][1] + time * vs[a[i]][1]; } context.beginPath(); context.moveTo(p0[0], p0[1]); context.lineTo(p1[0], p1[1]); context.lineTo(p2[0], p2[1]); context.closePath(); if (po == 0 || po == 1) { if (sgn > 0) { context.fillStyle = po ? "LightBlue" : "Gray"; context.fill(); } else if (sgn < 0) { context.fillStyle = po ? "LightCoral" : "Gray"; context.fill(); } } context.strokeStyle = "SaddleBrown"; context.stroke(); if (po == 2) { const c = point([0.333, 0.333, 0.334], [p0, p1, p2]); if (a[0] != a[1]) { const e = point([0.5, 0.5, 0], [p0, p1, p2]); context.beginPath(); context.moveTo(c[0], c[1]); context.lineTo(e[0], e[1]); context.strokeStyle = cs[op(a[0], a[1])]; context.stroke(); } if (a[0] != a[2]) { const e = point([0.5, 0, 0.5], [p0, p1, p2]); context.beginPath(); context.moveTo(c[0], c[1]); context.lineTo(e[0], e[1]); context.strokeStyle = cs[op(a[0], a[2])]; context.stroke(); } if (a[1] != a[2]) { const e = point([0, 0.5, 0.5], [p0, p1, p2]); context.beginPath(); context.moveTo(c[0], c[1]); context.lineTo(e[0], e[1]); context.strokeStyle = cs[op(a[1], a[2])]; context.stroke(); } } } for (let i = 0; i < vertex.bary.length; ++i) { const p = point(vertex.bary[i]); p[0] = (1 - time) * p[0] + time * vs[vertex.color[i]][0]; p[1] = (1 - time) * p[1] + time * vs[vertex.color[i]][1]; context.beginPath(); context.arc(p[0], p[1], 8, 0, 2 * Math.PI, false); context.fillStyle = cs[vertex.color[i]]; context.fill(); } return context.canvas; }34:[] 31:{"id":"5e3c2b860d1142c1","slug":"sperners-lemma","title":"Sperner’s Lemma","thumbnail":"586f49ecf4a6c1687eee9bad60f78b362053c77a80f5b22c5518c67dcbfcf357","access_level":"public","create_time":"$D2022-12-22T17:48:58.070Z","update_time":"$D2023-01-05T17:34:40.844Z","view_time":null,"first_public_time":"$D2022-12-22T17:48:58.070Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"7a4ecd430a93cd6f","login":"vinicius-mello","name":"Vinícius Mello","avatar_url":"https://avatars-next.observableusercontent.com/b5d4671aa488d8bcb984f575f985332403cde5f63942ea883a6a1a630941ec05","tier":"starter_2024"},"version":158,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"ecc4854ab7ad95b6","login":"vinicius-mello","name":"Vinícius Mello","avatar_url":"https://avatars-next.observableusercontent.com/b5d4671aa488d8bcb984f575f985332403cde5f63942ea883a6a1a630941ec05","tier":null}],"members":[{"type":"individual","id":"ecc4854ab7ad95b6","login":"vinicius-mello","name":"Vinícius Mello","avatar_url":"https://avatars-next.observableusercontent.com/b5d4671aa488d8bcb984f575f985332403cde5f63942ea883a6a1a630941ec05","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Sperner’s Lemma","cells":[{"id":0,"value":"# Sperner’s Lemma","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"viewof m = Inputs.range([1, 16], { label: \"Subdivision\", step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"viewof po = Inputs.radio(\n new Map([\n [\"Parity\", 0],\n [\"Orientation\", 1],\n [\"Dual Graph\", 2],\n [\"Nothing\", -1]\n ]),\n { value: 0 }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"viewof time = Inputs.range([0, 1], { label: \"t\", step: 0.01, value: 0 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"viewof random = Inputs.button(\"Random\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"[video](https://av.tib.eu/media/11510)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"vertex = {\n function getRandomInt(max) {\n return Math.floor(Math.random() * max);\n }\n random;\n let a = [m, 0, 0];\n let r = {\n bary: [],\n color: [],\n idx: {}\n };\n let i = 0;\n do {\n const t = a.slice();\n let c;\n do {\n c = getRandomInt(3);\n } while (t[c] == 0);\n const bary = t.map((x) => x / m);\n r.bary.push(bary);\n r.color.push(c);\n r.idx[t.toString()] = i;\n i++;\n } while (next_triangular(m, a));\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"triangle = {\n let a = [m - 1, 0, 0];\n let r = [];\n do {\n const b0 = a.slice();\n b0[0] += 1;\n const b1 = a.slice();\n b1[1] += 1;\n const b2 = a.slice();\n b2[2] += 1;\n r.push([\n vertex.idx[b0.toString()],\n vertex.idx[b1.toString()],\n vertex.idx[b2.toString()]\n ]);\n } while (next_triangular(m - 1, a));\n a = [m - 2, 0, 0];\n if (m - 2 < 0) return r;\n do {\n const b0 = a.slice();\n b0[1] += 1;\n b0[2] += 1;\n const b1 = a.slice();\n b1[0] += 1;\n b1[2] += 1;\n const b2 = a.slice();\n b2[0] += 1;\n b2[1] += 1;\n r.push([\n vertex.idx[b0.toString()],\n vertex.idx[b1.toString()],\n vertex.idx[b2.toString()]\n ]);\n } while (next_triangular(m - 2, a));\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"function next_triangular(m, v) {\n const N = v.length - 1;\n if (v[N] == m) return false;\n let r;\n for (r = N - 1; r >= 0; --r) if (v[r] != 0) break;\n v[r] = v[r] - 1;\n for (let j = r + 1; j <= N; ++j) v[j] = 0;\n v[r + 1] = m;\n for (let j = 0; j <= r; ++j) v[r + 1] -= v[j];\n return true;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"function permsgn(p) {\n const n = p.length;\n var sgn = 1;\n for (var i = 0; i < n; ++i) {\n for (var j = 0; j < i; ++j) {\n if (p[i] < p[j]) {\n sgn = -sgn;\n } else if (p[i] === p[j]) {\n return 0;\n }\n }\n }\n return sgn;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"