3 ms·

Flipping until you are lost

102 points by greghn 4y ago

onos 4y ago
Interesting scaling as diffusion in a uniform space goes like x^2 ~ t, or t~x^1/2. So I’d expect the time to equilibrate to go like a length to the 1/2. Maybe that works out if the length is some power of n in this case? Or maybe this space is just very different from a uniform one.
goldenkey 4y ago
This work is subtly related to chaos theory. The nth coefficient of the ith Mandelbrot polynomial lemniscate [3] is equal to the number of possible binary trees with n nodes of height i or less. This is because z -> z^2 + c reflects coefficients recursively produced by repeated applications of the binomial theorem. When n becomes <= i, the nth coefficient stabilizes, converging to the nth Catalan number, which is the number of possible binary trees with n nodes. The nth Catalan number is also the number of triangulations of an n+2-gon. https://en.m.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics https://en.m.wikipedia.org/wiki/Catalan_number#Applications_... Now, there is a 1-to-1 bijective mapping between binary trees of height n and node count i, and n+2 sided polygon triangulations with i segments. https://www.r-bloggers.com/2015/07/catalan-numbers-fortriangulationsgamblers-ruinbinary/ https://www.r-bloggers.com/2015/07/catalan-numbers-fortriang... In fact, the same associahedron in "Flipping until you are lost" is mentioned here: https://www.researchgate.net/figure/The-bijection-between-binary-plane-trees-and-triangulations-of-a-polygon-as_fig1_225917464 https://www.researchgate.net/figure/The-bijection-between-bi... What is the significance of all of this? There is currently no closed form approximation for these numbers. As simple as it might sound, we have no closed form for the number of binary trees with i nodes of height <= n. If we did, we could approximate the Mandelbrot and it would unlock new frontiers of understanding chaos theory. Philippe Flajolet, a now-deceased titan of analytic combinatorics [2] wrote some papers on the problem, but never got more than rough asymptotic bounds. https://www.sciencedirect.com/science/article/pii/0022000082900046 https://www.sciencedirect.com/science/article/pii/0022000082... Further work was done here: https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf When I saw this, my eyes lit up. It is late but in the morning I will have to see if the findings in this paper help at all with the above problem. ------- [1] https://en.wikipedia.org/wiki/Philippe_Flajolet https://en.wikipedia.org/wiki/Philippe_Flajolet [2] https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics... [3] http://www.mrob.com/pub/muency/lemniscates.html http://www.mrob.com/pub/muency/lemniscates.html
quietbritishjim 4y ago
Interesting article. I wasn't even properly familiar with triangulation of (convex) polygons. I knew it was possible because 3d games triangulate things all the time. What I didn't realise is that there is a fixed number of triangles in a triangulation of a polygon. I had assumed the word "minimal" had been missing at first, but looking at the pictures I realised it would be impossible to add an extra one (unless you introduce a vertex by intersecting a line with the middle of an existing line)

102 points by greghn 4y ago

onos 4y ago

Interesting scaling as diffusion in a uniform space goes like x^2 ~ t, or t~x^1/2. So I’d expect the time to equilibrate to go like a length to the 1/2. Maybe that works out if the length is some power of n in this case? Or maybe this space is just very different from a uniform one.

goldenkey 4y ago

This work is subtly related to chaos theory. The nth coefficient of the ith Mandelbrot polynomial lemniscate [3] is equal to the number of possible binary trees with n nodes of height i or less. This is because z -> z^2 + c reflects coefficients recursively produced by repeated applications of the binomial theorem. When n becomes <= i, the nth coefficient stabilizes, converging to the nth Catalan number, which is the number of possible binary trees with n nodes. The nth Catalan number is also the number of triangulations of an n+2-gon. https://en.m.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics https://en.m.wikipedia.org/wiki/Catalan_number#Applications_... Now, there is a 1-to-1 bijective mapping between binary trees of height n and node count i, and n+2 sided polygon triangulations with i segments. https://www.r-bloggers.com/2015/07/catalan-numbers-fortriangulationsgamblers-ruinbinary/ https://www.r-bloggers.com/2015/07/catalan-numbers-fortriang... In fact, the same associahedron in "Flipping until you are lost" is mentioned here: https://www.researchgate.net/figure/The-bijection-between-binary-plane-trees-and-triangulations-of-a-polygon-as_fig1_225917464 https://www.researchgate.net/figure/The-bijection-between-bi... What is the significance of all of this? There is currently no closed form approximation for these numbers. As simple as it might sound, we have no closed form for the number of binary trees with i nodes of height <= n. If we did, we could approximate the Mandelbrot and it would unlock new frontiers of understanding chaos theory. Philippe Flajolet, a now-deceased titan of analytic combinatorics [2] wrote some papers on the problem, but never got more than rough asymptotic bounds. https://www.sciencedirect.com/science/article/pii/0022000082900046 https://www.sciencedirect.com/science/article/pii/0022000082... Further work was done here: https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf When I saw this, my eyes lit up. It is late but in the morning I will have to see if the findings in this paper help at all with the above problem. ------- [1] https://en.wikipedia.org/wiki/Philippe_Flajolet https://en.wikipedia.org/wiki/Philippe_Flajolet [2] https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics... [3] http://www.mrob.com/pub/muency/lemniscates.html http://www.mrob.com/pub/muency/lemniscates.html

quietbritishjim 4y ago

Interesting article. I wasn't even properly familiar with triangulation of (convex) polygons. I knew it was possible because 3d games triangulate things all the time. What I didn't realise is that there is a fixed number of triangles in a triangulation of a polygon. I had assumed the word "minimal" had been missing at first, but looking at the pictures I realised it would be impossible to add an extra one (unless you introduce a vertex by intersecting a line with the middle of an existing line)