Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Flipping until you are lost (11011110.github.io)
102 points by greghn on July 28, 2022 | hide | past | favorite | 3 comments



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)


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.


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_...

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-fortriang...

In fact, the same associahedron in "Flipping until you are lost" is mentioned here: 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/0022000082...

Further work was done here: 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

[2] https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics...

[3] http://www.mrob.com/pub/muency/lemniscates.html




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: