Uploaded November 2026 | Updated November 2026, 8 hours ago
This is the 2100th video published on this channel, not counting a handful of videos published multiple times because of compression issues. As usual for a milestone, I tried to implement something new.
This time, I followed up on a suggestion that came up in comments many times, which is to plot Voronoi tesselations of the moving particles. Consider a collection of points in the plane. The Voronoi cell of a given point is the set of points in the plane that are closer to the chosen point than any other in the collection. It is a convex polygon, whose sides are parts of mediators of the chosen point and another point in the collection.
Computing Voronoi cells in an efficient way is not straightforward. I asked around, and was told that a good way of constructing the tesselation is Fortune's algorithm (see links below), invented by Steven Fortune in 1986. The basic idea is that a straight line called sweep line is moved through the points, say from left to right. Whenever it encounters a point (this is called a site event), a parabola is created, which is equidistant from the point and the sweep line, and changes over time. The rightmost parabolic arcs form the so-called beach line. Whenever one of the arcs is squeezed, one has found a vertex of the tesselation, which is equidistant from three points. This is called a circle event. The algorithm creates and deletes site and circle events as needed, that are stored in a queue by increasing x coordinate, and terminates when the queue is empty.
When coded optimally, Fortune's algorithm has complexity n*log(n), where n is the number of points. My implementation is not optimal because I did not code the insertion of parabolas in the most efficient way, and should have complexity n^{3/2}.
The simulation shows particles interacting via a Lennard-Jones potential and coupled to a thermostat whose temperature decreases and increases several times. One can see grain boundaries forming, due to the boundary conditions - the particles are confined to a rectangular box. Occasionally, the algorithm misses a point, which may be due to several events being simultaneous.
This simulation has four parts, showing the same evolution with two different visualizations:
Voronoi cells, number of sides: 0:00
Voronoi cells, kinetic energy: 1:40
Particles, number of neighbors: 3:24
Particles, kinetic energy: 5:04
Parts 1 and 2 show the Voronoi tesselation, with the color of cells depending first on the number of its sides (light blue for hexagons, a darker blue for heptagons, green for pentagons, yellow for squares and dark blue-purple for octagons), and then on the kinetic energy. Note that hexagons, pentagons and heptagons are the most common shapes. Parts 3 and 4 only show the particles with lines connecting nearest particles, and colors depending first on the number of nearby particles, and then on the kinetic energy.
The temperature is controlled by a thermostat, implemented here with the "Nosé-Hoover-Langevin" algorithm introduced by Ben Leimkuhler, Emad Noorizadeh and Florian Theil, see reference below. The idea of the algorithm is to couple the momenta of the system to a single random process, which fluctuates around a temperature-dependent mean value. Lower temperatures lead to lower mean values. To save on computation time, particles are placed into a "hash grid", each cell of which contains between 3 and 10 particles. Then only the influence of other particles in the same or neighboring cells is taken into account for each particle.
Render time: Parts 1 and 2 - 6 minutes 37 seconds
Parts 3 and 4 - 8 minutes 23 seconds
Color scheme: Turbo, by Anton Mikhailov
gist.github.com/mikhailov-work/6a308c20e494d9e0ccc29036b28faa7a
Music: "Wolf Moon" by the Unicorn Heads@/UCbdU8d-QYGeEseYLlrSy8KQ
Info on Fortune's algorithm:
pvigier.github.io/2018/11/18/fortune-algorithm-details.html
jacquesheunis.com/post/fortunes-algorithm
blog.ivank.net/fortunes-algorithm-and-implementation.html
Steven Fortune's original article: wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf
Thermostat reference: Leimkuhler, B., Noorizadeh, E. & Theil, F. A Gentle Stochastic Thermostat for Molecular Dynamics. J Stat Phys 135, 261–277 (2009). doi.org/10.1007/s10955-009-9734-0
maths.warwick.ac.uk/~theil/HL12-3-2009.pdf
Current version of the C code used to make these animations:
github.com/nilsberglund-orleans/YouTube-simulations
https://www.idpoisson.fr/berglund/software.html
Some outreach articles on mathematics:
https://images.math.cnrs.fr/_Berglund-Nils-1343_.html
(in French, some with a Spanish translation)
This is the 2100th video published on this channel, not counting a handful of videos published multiple times because of compression issues. As usual for a milestone, I tried to implement something new.
This time, I followed up on a suggestion that came up in comments many times, which is to plot Voronoi tesselations of the moving particles. Consider a collection of points in the plane. The Voronoi cell of a given point is the set of points in the plane that are closer to the chosen point than any other in the collection. It is a convex polygon, whose sides are parts of mediators of the chosen point and another point in the collection.
Computing Voronoi cells in an efficient way is not straightforward. I asked around, and was told that a good way of constructing the tesselation is Fortune's algorithm (see links below), invented by Steven Fortune in 1986. The basic idea is that a straight line called sweep line is moved through the points, say from left to right. Whenever it encounters a point (this is called a site event), a parabola is created, which is equidistant from the point and the sweep line, and changes over time. The rightmost parabolic arcs form the so-called beach line. Whenever one of the arcs is squeezed, one has found a vertex of the tesselation, which is equidistant from three points. This is called a circle event. The algorithm creates and deletes site and circle events as needed, that are stored in a queue by increasing x coordinate, and terminates when the queue is empty.
When coded optimally, Fortune's algorithm has complexity n*log(n), where n is the number of points. My implementation is not optimal because I did not code the insertion of parabolas in the most efficient way, and should have complexity n^{3/2}.
The simulation shows particles interacting via a Lennard-Jones potential and coupled to a thermostat whose temperature decreases and increases several times. One can see grain boundaries forming, due to the boundary conditions - the particles are confined to a rectangular box. Occasionally, the algorithm misses a point, which may be due to several events being simultaneous.
This simulation has four parts, showing the same evolution with two different visualizations:
Voronoi cells, number of sides: 0:00
Voronoi cells, kinetic energy: 1:40
Particles, number of neighbors: 3:24
Particles, kinetic energy: 5:04
Parts 1 and 2 show the Voronoi tesselation, with the color of cells depending first on the number of its sides (light blue for hexagons, a darker blue for heptagons, green for pentagons, yellow for squares and dark blue-purple for octagons), and then on the kinetic energy. Note that hexagons, pentagons and heptagons are the most common shapes. Parts 3 and 4 only show the particles with lines connecting nearest particles, and colors depending first on the number of nearby particles, and then on the kinetic energy.
The temperature is controlled by a thermostat, implemented here with the "Nosé-Hoover-Langevin" algorithm introduced by Ben Leimkuhler, Emad Noorizadeh and Florian Theil, see reference below. The idea of the algorithm is to couple the momenta of the system to a single random process, which fluctuates around a temperature-dependent mean value. Lower temperatures lead to lower mean values. To save on computation time, particles are placed into a "hash grid", each cell of which contains between 3 and 10 particles. Then only the influence of other particles in the same or neighboring cells is taken into account for each particle.
Render time: Parts 1 and 2 - 6 minutes 37 seconds
Parts 3 and 4 - 8 minutes 23 seconds
Color scheme: Turbo, by Anton Mikhailov
gist.github.com/mikhailov-work/6a308c20e494d9e0ccc29036b28faa7a
Music: "Wolf Moon" by the Unicorn Heads@/UCbdU8d-QYGeEseYLlrSy8KQ
Info on Fortune's algorithm:
pvigier.github.io/2018/11/18/fortune-algorithm-details.html
jacquesheunis.com/post/fortunes-algorithm
blog.ivank.net/fortunes-algorithm-and-implementation.html
Steven Fortune's original article: wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf
Thermostat reference: Leimkuhler, B., Noorizadeh, E. & Theil, F. A Gentle Stochastic Thermostat for Molecular Dynamics. J Stat Phys 135, 261–277 (2009). doi.org/10.1007/s10955-009-9734-0
maths.warwick.ac.uk/~theil/HL12-3-2009.pdf
Current version of the C code used to make these animations:
github.com/nilsberglund-orleans/YouTube-simulations
https://www.idpoisson.fr/berglund/software.html
Some outreach articles on mathematics:
https://images.math.cnrs.fr/_Berglund-Nils-1343_.html
(in French, some with a Spanish translation)
