{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# An Optimal Algorithm for the Freeze-Tag Problem in 2D" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "plt.figure(figsize=(1,1))\n", "plt.plot([])" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "#import matplotlib.pyplot as plt\n", "#plt.plot([])\n", "\n", "# Warning! Constants are imported as constant only, so 'from ... import *' will not work properly\n", "import freeze_tag_mini as ft\n", "from math import pi, sin, cos" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Optimal wake-up times for $n$ points regularly spaced on the unit circle ($\\ell_2$ norm)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in range(0,12):\n", " P = ft.generate_regular_polygon(n) + [(0,0)] # a circle and its center\n", " x,T = ft.optimal_tree(n,P,ft.dist_L2) # compute the optimal tree\n", " print(f\"regular({n}) = {x:.3f}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lower bound for $\\ell_p$ norm" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.LP_NORM = 1.5 # p for L_p\n", "ft.SEED = -1 # do not display seed\n", "ft.PROCESS_TIME = 0 # elapsed time in seconds in display draw_all()\n", "\n", "P = [(0,0)] # the center of the circle\n", "if 1 <= ft.LP_NORM <= 2:\n", " P += [(1,0),(0,1),(-1,0),(0,-1)]\n", "else:\n", " u = 1/2**(1/ft.LP_NORM)\n", " P += [(u,u),(-u,u),(-u,-u),(u,-u)]\n", "\n", "x,T = ft.optimal_tree(0,P,ft.dist_Lp)\n", "u = 1 + 2**(1+max(1/ft.LP_NORM,1-1/ft.LP_NORM))\n", "ft.draw_all(f'norm L_p, p = {ft.LP_NORM}\\nconjecture = {u:.3f}\\nlower bound',x,T)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lower bound in $\\ell_1$ norm for a square of diameter $1$ with $6+1$ points with wake-up time $2+1/6$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.SEED = -1 # does not display seed\n", "ft.PROCESS_TIME = 0 # elapsed time in seconds for display draw_all()\n", "\n", "eps=1/12 # best value, if eps=1/6 => depth = 2.000\n", "P = [\n", " (0,0),(1/2,1/2),(1/2,-1/2),(1,0), # p0,p2,p5,p4 (the square)\n", " (1/2-eps, 1/2-eps), # p1\n", " (1-2*eps, -2*eps), # p3\n", " (1/2+2*eps, -1/2+2*eps), # p6\n", " ]\n", "\n", "x,T = ft.optimal_tree(0,P,ft.dist_L1)\n", "ft.draw_all('optimal',x,T)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The complete binary tree is not always optimal even if $n = 2^k-1$, here in $\\ell_2$ norm" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.init_seed(2074) # set SEED\n", "n = 2**3 - 1 # number of points (asleep robots)\n", "P = ft.generate_von_mises(n,0.5) # uniformly random on the disc\n", "ft.normalize_bc(P, ft.dist_L2) # add ROOT = (0,0) at the end of the list POINTS\n", "x,T = ft.optimal_tree() # compute the optimal tree\n", "ft.draw_all('optimal',x,T) # display results" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### $n=4$ points in convex position having a crossing (apart from the first edge)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.init_seed(5687) # set SEED\n", "P = ft.generate_convex(4) # points in convex position\n", "ft.normalize_bc(P, ft.dist_L2) # add ROOT = (0,0) at the end of the list POINTS\n", "x,T = ft.optimal_tree() # compute the optimal tree\n", "ft.draw_all('optimal',x,T) # display results" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### $n=11$ points in convex position having $3$ crossings (apart from the first edge)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.init_seed(3906) # set SEED\n", "n = 11 # number of points (asleep robots)\n", "P = ft.generate_convex(n) # points in convex position\n", "ft.normalize_bc(P, ft.dist_L2) # add ROOT = (0,0) at the end of the list POINTS\n", "x,T = ft.optimal_tree() # compute the optimal tree\n", "ft.draw_all('convex pts') # draw the points\n", "ft.draw_all('optimal',x,T,save='fig.svg') # draw the tree and save it the figure\n", "# T = [11, [5, [6, [7, [8, [9], [10]], [4]], [3, [2]]], [0, [1]]]]\n", "# T = [11, [5, [6, [7, [8, [9], [10]], [4]], [0, [1]]], [3, [2]]]]\n", "# ft.draw_all('???????',x,T)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### A tree with a 'controlled' shape in $\\ell_2$ norm" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.SEED=-1 # no seed to display\n", "h, eps = 20, 0.2\n", "P = [\n", " (0,-1), (0,h),\n", " (+eps,1), (+h-1,1),\n", " (-eps,3), (-h+3,3),\n", " (+eps,5), (+h-5,5),\n", " (-eps,7), (-h+7,7),\n", " (+eps,9), (+h-9,9),\n", " #(-eps,11), (-h+11,11) # works, but time consuming\n", " ]\n", "x,T = ft.optimal_tree(0,P,ft.dist_L2)\n", "ft.draw_all('optimal',x,T,disc=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lower bounds for odd $n = 2k+1$ points on a circle (in $\\ell_2$ norm) showing that the worst-case on a circle is not the uniform case for $n$ odd\n", "\n", "The generic counter-example (see cell below) has $2k$ angles of value $x$ plus one of angle of value $y$, $0 < y < x$. So $2kx + y = 2\\pi = nx - \\varepsilon$, where $\\varepsilon = x - y$. If $\\varepsilon=0$ (or $x=y$), then this is the uniform case. To find the optimal $\\varepsilon$, we start by searching for it experimentally using binary search with optimal_tree(). Then, we observe the longest branches in the tree solutions (we sum the chords lengths) with some $\\varepsilon_1 < \\varepsilon$, then with some $\\varepsilon_2 > \\varepsilon$. This gives to us equations ($E_1$) and ($E_2$) respectively. The solution of $E_1 = E_2$ (approximated by Maple) confirms the value of optimal $\\varepsilon$. Here, $\\mathrm{chord}(x) = 2\\sin(x/2)$ denotes the length of the chord for an angle of $x$. Note that $\\mathrm{chord}(y) = \\mathrm{chord}(kx)$, and that we must have $x \\in [2\\pi/n,\\pi/k]$. The solutions around the optimal $\\varepsilon$ are without crossovers in general, except for $k=2$ with the $\\mathrm{chord}(y) + \\mathrm{chord}(y+x)$ branch. The same methodology can be applied for other norms, like $\\ell_1$.\n", "\n", "Here are the best values for $\\varepsilon = \\varepsilon(k)$ obtained so far:\n", "\n", "---\n", "- $n=3~(k=1)$\n", "- $\\varepsilon=0$ => depth = $2.732$ (uniform case)\n", "- $\\varepsilon=𝜋$ => depth = $3.000$ (worst-case)\n", "\n", "---\n", "- $n=5~(k=2)$\n", "- $\\varepsilon=0$ => depth = $3.351$ (uniform case)\n", "- $\\varepsilon=0.5827617039$ => depth = $3.535628694$ (worst-case)\n", "- $x$ is root of $2\\mathrm{chord}(x) = \\mathrm{chord}(y) + \\mathrm{chord}(y+x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/5,\\pi/2]$\n", "- [ $x=1.373189402, y=0.7904276980$ ]\n", "- NB. $\\mathrm{chord}(y+x) = \\mathrm{chord}(3x)$, and the tree solution for $> \\varepsilon$ has a crossing.\n", "\n", "---\n", "- $n=7~(k=3)$\n", "- $\\varepsilon=0$ => depth = $3.431$ (uniform case)\n", "- $\\varepsilon=0.3784299788$ => depth = $3.544911380$ (worst-case)\n", "- $x$ is root of $\\mathrm{chord}(x) + \\mathrm{chord}(2x) = \\mathrm{chord}(y) + \\mathrm{chord}(3x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/7,\\pi/3]$\n", "- [ $x=0.9516593267, y=0.5732293479$ ]\n", "\n", "---\n", "- $n=9~(k=4)$\n", "- $\\varepsilon=0$ => depth = $3.416$ (uniform case)\n", "- $\\varepsilon=0.2814874303$ => depth = $3.490388052$ (worst-case)\n", "- $x$ is root of $\\mathrm{chord}(x) + \\mathrm{chord}(3x) = \\mathrm{chord}(y) + \\mathrm{chord}(x) + \\mathrm{chord}(2x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/9,\\pi/4]$\n", "- [ $x=0.7294080820, y=0.5732293479$ ]\n", "\n", "---\n", "- $n=11~(k=5)$\n", "- $\\varepsilon=0$ => depth = $3.383$ (uniform case)\n", "- $\\varepsilon=0.2991993005$ => depth = $3.451257847$ (worst-case)\n", "- $x$ is root of $\\mathrm{chord}(x) + \\mathrm{chord}(4x) = \\mathrm{chord}(y) + \\mathrm{chord}(x) + \\mathrm{chord}(3x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/11,\\pi/5]$\n", "- [ $x=0.5983986008, y=0.2991993003$, NB. $y=\\varepsilon$, soit $x=2y$ ]\n", "\n", "---\n", "- $n=13~(k=6)$\n", "- $\\varepsilon=0$ => depth = $3.349$ (uniform case)\n", "- $\\varepsilon=0.2940862069$ => depth = $3.407695572$ (worst-case)\n", "- $x$ is root of $\\mathrm{chord}(x) + \\mathrm{chord}(5x) = \\mathrm{chord}(y) + \\mathrm{chord}(x) + \\mathrm{chord}(4x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/13,\\pi/6]$\n", "- [ $x=0.5059439627, y=0.2118577558$ ]\n", "\n", "---\n", "- $n=15~(k=7)$\n", "- $\\varepsilon=0$ => depth = $3.318$ (uniform case)\n", "- $\\varepsilon=0.2453594624$ => depth = $3.392885535$ (worst-case)\n", "- $x$ is root of $2\\mathrm{chord}(x) + \\mathrm{chord}(4x) = \\mathrm{chord}(y) + \\mathrm{chord}(x) + \\mathrm{chord}(5x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/15,\\pi/7]$\n", "- [ $x=0.4352363180, y=0.1898768556$ ]\n", "\n", "---\n", "- $n=17~(k=8)$\n", "- $\\varepsilon=0$ => depth = $3.331$ (uniform case)\n", "- $\\varepsilon=0.1920896074$ => depth = $3.386640398$ (worst-case)\n", "- $x$ is root of $2\\mathrm{chord}(x) + \\mathrm{chord}(5x) = \\mathrm{chord}(y) + \\mathrm{chord}(6x)$, where $y = 2\\pi - 2kx$, and $x\\in[2\\pi/17,\\pi/8]$\n", "- [ $x=0.3808985244, y=0.1888089170$ ]\n", "\n", "---" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ft.SEED = -1 # do not display SEED\n", "ft.PROCESS_TIME = 0 # elapsed time temps to display in draw_all()\n", "\n", "k = 3\n", "n = 2*k + 1\n", "eps = 0.3784299788 # x-y\n", "x = (2*pi+eps)/n # angle x\n", "# x = 0.37\n", "# eps = n*x - 2*pi\n", "print(f\"x = {x}, but should be in [{2*pi/n:.4f},{pi/k:.4f}]\")\n", "if x < 2*pi/n or x > pi/k: quit()\n", "P = [(0,0),(1,0)] # root and first point\n", "t = 0\n", "for i in range(k):\n", " t += x\n", " P += [(cos(t),sin(t)),(cos(t),-sin(t))] # add two points \n", "\n", "x,T = ft.optimal_tree(0,P,ft.dist_L2)\n", "ft.draw_all('optimal',x,T,save='fig.svg')\n", "\n", "# A more general construction, still for n = 2k+1 points. Chords are symmetric from (1,0) and are composed of k-1 chords of angle x1, followed by one of angle x2, and then the remaining. It happens that the worst-case is whenever there is only one chord of angle < 2𝜋/n and all the other greater and equal.\n", "\n", "# k=3 # Best: 3.544911380, eps1 = eps2 = 0.3784299788\n", "# k=4 # Best: 3.490388052, eps1 = eps2 = 0.2814874303\n", "# k=6 # Best: 3.407695572, eps1 = eps2 = 0.2940862069\n", "# k=7 # Best: 3.392885535, eps1 = eps2 = 0.2453594624\n", "# eps1, eps2 = 0.3, 0.1\n", "# n = 2*k + 1\n", "# x1 = (2*pi+eps1)/n\n", "# x2 = (2*pi+eps2)/n\n", "# P = [(0,0),(1,0)]\n", "# t = 0\n", "# for i in range(k):\n", "# if ixmax:\n", " xmax,Tmax,Pmax = x,T,ft.POINTS\n", " print(f\"x = {x}\")\n", " print(f\"T = {T}\")\n", " print(f\"ft.POINTS = {ft.POINTS}\")\n", "\n", "# Maximum for ft.generate_von_mises(8,0,8,10) with NB = 10,000\n", "# x = 3.570593145854709\n", "# T = [0, [4, [3, [8, [2]], [7]], [5, [1], [6]]]]\n", "# ft.POINTS = [(0.0, 0.0), (-0.9985549564600698, 0.011827106584179929), (-0.006175724711713601, -0.9996790979426582), (0.9996797961518151, 0.018006435511381674), (0.7213105266396888, 0.6916888441126671), (-0.7102685631588145, 0.7017728500934621), (-0.040494833692801824, 0.9979330572465028), (-0.6851648746614944, -0.7272314994841055), (0.7196686298933903, -0.69431769612143)]\n", "\n", "# Maximum for ft.generate_von_mises(8,0.1) with NB = 10,000\n", "# (many crossings ...)\n", "# x = 3.0498501436246337\n", "# T = [0, [3, [1, [8, [2]], [7]], [5, [4], [6]]]]\n", "# ft.POINTS = [(0.0, 0.0), (-0.38313149525860823, -0.8944996655519788), (0.24967021557384517, 0.9683309266233882), (-0.1987667780636083, -0.8715771404052549), (-0.9335487858180874, 0.25552358830278954), (-0.6785219343019202, -0.6434257547307705), (0.8959422895728233, -0.26045916474825553), (0.7954899585093611, 0.5057387380199572), (0.2528665297861946, 0.9403684724901246)]\n", "\n", "x,T,ft.POINTS = xmax,Tmax,Pmax\n", "ft.draw_all('optimal',x,T)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" }, "orig_nbformat": 4 }, "nbformat": 4, "nbformat_minor": 2 }