12:50 This is a beautiful series of animations. This whole video is informative and profound, thank you for making it.

I thoroughly enjoyed your presentation. There's a relationship between the Voronoi and the way soap films optimize the partitioning of space. Where soap films add an interesting dimension to the optimization process, is that they will further optimize the partitioning by *adding* cells to minimize a cost function. Whereas Voronoi starts with a known set of foci and defines the optimal boundaries between these, soap films add foci to make the overall pattern more stable/homogenous. Applied to business, (for instance to your map of Manhattan) this would help define the "ghost" foci that are needed to further optimize the cost for *any* point within a cell, to reach its nearest focus. In the absolute, this process would rearrange the foci according to a Poisson distribution, but in practice, the cost doesn't have to be perfectly uniform and some degree of heterogeneity is always accepted/imposed by the system. To summarize ; imagine the Voronoi partitioning process, blended with a Poisson estimator that works on the foci. You'd dial the degree of homogeneity acceptable by your "customers", and you'd see ghost foci appear, exactly where in theory they are needed. Now, in the real world, "homogeneity" is not a simple euclidian (or discrete/taxicab) process ; the actual "map" of supply, demand and cost warps the cartesian space you are operating in : Your beautiful math needs to be applied to the "unwarped" map, and the result warped back to the real world configuration. This is the reason that in nature, and clearly in human environments, we rarely see resources that are placed (spatially and temporally) according to a pure Poisson distribution, but rather, following a log-normal distribution. The inequality of repartition seems to be indicative a a higher degree of process and demand optimization. You can see it in how paths on the ground tend to be distributed more like neurons and dendrites, than as a regular tessellation. Ultimately, the Voronoi process therefore is only the first stage in the optimisation process ; it needs to be blended with a Poisson cost function, and this in turn, this needs to be "warped" according to the influence of a myriad other constraints such as demand. But I would argue that this third step is best left to natural processes : Your beautiful mathematical planning should find the optimal distribution, regardless of demand, and this would be sufficient to define where the unseen opportunities *could* be. Test then your assumptions in real life and let natural processes decide which ones of these ghost foci are indeed viable, and even if their position needs to be skewed. Another way to look at his is to think of optimal segmentation/distribution in an n-dimensional manifold ; which is what we do with Principal Component Analysis, but nowadays, totally core to what Machine Learning is based on. Think of your Voronoi boundaries as the segmentation obtained by gradient descent in a neural network. I love algebraic and analytical solutions because of their intrinsic beauty, and how they connect abstract phenomena to meaningful principles, but more ant more it is becoming obvious that ML is better suited to these sorts of tasks where the number of dimensions to consider becomes unwieldy. It's frustrating to see a ML algorithm absolutely nail the solution to an intractable problem, because the ML solution is a semantic black box ; but we're going to have to live with this until we find ways to parametrize neural networks according to higher-order semantics.

There are a few animation glitches (particularly mixing up the min and max functions) and audio issues, but overall I think this video does a pretty good job at explaining the concepts necessary to understand Fortune's Algorithm. Also, seeing the Manhattan-distance Voronoi diagram was pretty interesting.

The video is great! The graphics were really nice, and the explanation very in depth. I'm going to have to watch it again just to make sense of it all! A couple of years ago, I tried implementing Fortunes Algorithm, but wasn't very successful. I think I'll give it a try again because of this video!

Fortune's Algorithm is one of my favorite algorithms of all time ! I got hooked on it when I was 18 and reimplemented it 3 months ago, being 24! Seeing this video taught me a lot of nice things I didn't know about, thank you and hats off :)

BEST some2 video BY FAR! i genuinely hope you win

Incredible animations! Never imagined that the algorithm is the equivalent of sweeping a plane through cones. Also, I really enjoyed that you extended the definition with the Manhattan bit.

I want more explanation and use of great functions! Great animation!

@11:08 a circle is an ellipse whose two foci are the same. This is a beautiful walk through, more like a fly over. Beautiful graphics, examples, and explanations on many levels, and interesting to see how the Voronoi algorithm applies to nature, even surprisingly the formation of metal crystals. Thanks!

while the animations and concept for the video are great, there are a couple of things holding it back: 1. the music gets a bit distracting at times 2. the video lacks focus. is your goal to explain Varanoi patterns? conic sections? some beautiful relationship between them? or something else? I can't easily tell...

This is pretty awesome. I've been thinking about Vornoi diagrams and wondered how they are composed so quickly, and this is a really good answer with a good explanation. I did run into the problem where you said directrix so many times it stopped feeling like a word, but I regained focus, relistened and mostly got it. Also, I see you using O(n) to as shorthand for "the complexity for n elements", like when you wrote O(n) = nlogn. The proper use is to put the function that describes complexity inside the O, and write something like "the complexity is O(nlogn)" Finally, Debussy is a wonderful choice for music. The beginning even kinda syncs up, like once the screen is the messiest the music reaches its peak

When the parabollas intersect each other while moving the directrix, how do you get the location of the points at the cusp? (It is visually apparent for us but not for a computer) Do you have to use calculus to find the local minima?

12:50 Magic

Is the parabola method faster than drawing all the perpendicular bisectors and figuring out which segments to keep?

Brilliant! Mindblowing!

Beautiful animations and clear explanations.

Really cool ! thank you!

Wow...this is mind blowing! Well explained my friend!

Awesome video!!

Really cool!

Great video !

1:40 - this example there should be a better way where instead of going trough pixels your canvas is the road network graph, so you're looking at the diagram with distances within roads and I think it would be a lot nicer

Great video and interesting concept. I thought this was made with manim but surprised to see it was with Blender. Have you opened the source somewhere?

Great work

great video! Many really cool moments, especially the part revealing that the parabola is the intersection of y = x and the radius function. And I liked the part at the end with the Manhattan distance variation. The audio is pretty inconsistent and it's clear that most lines were recorded at different times and places but that's not a big issue

What if have different heights for the the cones? So that the centres of those cones will have different attraction?

brain broke amazing content

do what... omg i new we were going to calculate the node. but whattttttt i feel like ive been abducted by aliens

Sometimes music is louder than speaker...

Tbh the way you come up with parabolas is unintuitive and "artificial". I'd rather get parabolas the same way you introduced circles, but instead of min among distances to a point, you consider min of distances between focus points and a line (or max like in the video, where parabola goes downwards). Anyways, very nice visualization with cones. O(n) = n log n is wrong if you look up the definition of O-notations. The correct way to describe the time complexity is T(n) = O(n log n) where T(n) is the runtime.

First

Hello, first of all this video is really great! I dont know if you will even answer but i am doing my bachelors thesis on voronoi diagrams and fortunes algorithm in manhattan distance i am bit struggling to get some concepts. If you would be so kind would you write me back and maybe i will give you my email to help me a little bit ? Thanks a lot even for the video 👍