The Surprising Math Behind Voronoi Diagram Perimeters

Support me on Patreon! / purplemindcs
Tier levels include special roles in my Discord server, seeing your name on screen at the end of videos, and getting preview of upcoming content. I will be making frequent posts on Patreon about my next video, which is about a recent research result from a team at Carnegie Mellon University. The first sneak peek is live right now -- head over there to check it out.
If you'd like to aid the success channel, this is the best way to do it! Every contribution is sincerely, greatly appreciated.
This is episode "3B" in a series called "Brainstorm."
The topics for these videos are puzzle-style problems, broken into two parts each, a couple months apart.
-- In the first part, I introduce the problem, and you (the viewers!!!) try to solve the problem yourself, or at least come up with some initial approaches, first steps, or partial solutions.
-- In the second part (this video), I follow up with animated discussions of the solutions that were sent to me, mixed in with my own thoughts.
The problem is about a beautiful geometric construct called a Voronoi Diagram (en.wikipedia.o..., formed from a set of "site" locations (points) in 2D space and a corresponding set of "cells" -- polygons which are the regions closest to the sites inside of them. The central question of the video is about finding the average perimeter of a random cell in a diagram with n uniformly random sites. As a community, we find that mathematically proving the answer to this question is extremely difficult, but experimental data suggest a very simple formula as a great approximation. Along the way, the journey leads us to rediscover a fundamental geometric quantity, ask questions about how circles overlap with squares, and find an approximation for a quite strange-looking five-dimensional integral.
Thanks so much to everyone who submitted something for this problem, and to everyone, in general, for watching the video! I’m planning on continuing this series, so stay tuned :)
Link to Meijering paper referenced in the video: pearl-hifi.com...
Brainstorm Episode 1A: • I dare you to try to s...
Brainstorm Episode 1B: • My Viewers Are Math Ge...
Brainstorm Episode 2A: • Dice Don't Normally Lo...
Brainstorm Episode 2B: • How to Make "Trick Dic...
Brainstorm Episode 3A (for this video): • Can You Solve This Geo...
Feel free to join my Discord server: / discord
Business Inquiries: [e-mail]
These animations are made using Manim, by 3Blue1Brown.

[@bearantarctic5843]

0:43 2:51 Holy shit that's my work, that's my fucking work omgggggg I'm happy that you found something useful in it even tho I misunderstood the question lmao

[@PurpleMindCS]

Thanks so much for submitting! Glad you enjoyed working on the problem and being a part of this video :)

[@willlagergaming8089]

This video got recommend ed to me atleast 6 times before i gave in

[@NoName-qf7lu]

18:17 I need to change that name😂

[@PurpleMindCS]

Hey! I tried to send you a message on Patreon about it :) Are you able to see it?

[@leif1075]

​@@PurpleMindCSPLEASE HELP HOW donyou not get BORED and FED UP with these long ass problems and HOW can I be as smart as Ramanujam or Einstrim amd make as grest.contributions or Inwill kill myself..hope you can pleqse respond

[@NoNameAtAll2]

hi, NoName!

[@dmit10]

Your viewers are gold

[@PurpleMindCS]

Very true.

[@paridhaxholli]

5:05 To determine if a point is inside or outside a closed shape, a ray is drawn. If the line intersects the shape (non tangentially) an odd number of times, the point is inside and the opposite for even. This step is done for every point.

[@danielgostein3039]

Bingo!

[@Keldor314]

Of course, this doesn't work for every closed shape. Some shapes, in particular fractals, can intersect the line an infinite number of times, which will result in this test not giving us an answer. But even in these cases, the shape can have a definite inside and outside, we just need to find a different way of testing it.

[@paridhaxholli]

@@Keldor314 Voronoi diagrams are never fractals

[@MaxG628]

@@paridhaxholli Can we say “by convexity” or is further proof needed?

[@MaxG628]

The plumb line algorithm! You need a ray, not a line, starting at the point of interest and whose angle is arbitrary as long as it doesn’t intersect any vertex of the polygon. Then check the parity of edge crossings as described.

[@karavankessel]

17:22 Hi! That's my solution! Just want to make a correction. My "projection being uniform" assumption is wrong, but it's still okay! The non-uniformity becomes uniform if we consider all permutations of the cell positions, and we are, since we are taking the expected value over all possible randomized points! I'm pretty sure that's enough to make it rigorous, as the rest should follow from the fact that all cells are convex, and we know the expected mean width. Edit: The fact that I divide by sqrt(n) instead of n could use some rigor. It intuitively makes sense, as projecting 2D down to 1D quadratically increases the density of points, so we should start with sqrt(n) points to cancel that out. It even seems to work when n is not a perfect square, which is like we are finding the average distance between some fractional amount of points, whatever that means. Think of the voronoi cell locations as some uniform probability per m^2 over the square. To get the equivalent 1D uniform probability we have to correct the units, hence the square root.

[@ruudh.g.vantol4306]

Beware of Bertrand’s distribution paradox.

[@karavankessel]

​@@ruudh.g.vantol4306 Interesting paradox, I've dealt with similar trying to generate random line segments within [0,1). I think we're safe in this case. Also I feel strongly that Method 1 of the paradox is the most correct answer, as it does not over or under-count particular chords like the others. Method 2 counts each diameter twice, and there are infinite of them. And Method 3 under-counts by an infinite amount of diameters. Thanks for pointing me towards that!

[@numberbasher269]

lets have some more solvable problems next time...

[@misternoone6392]

he's gonna find a way to give us riemann hypothesis as the next problem

[@ordinaryrat]

@@misternoone6392 Nah thats way too easy. If the problem is already known about, then its too easy. He is going to go into the 8th dimension to get some problem for his viewers to work through while they sleep.

[@berlinisvictorious]

Lmao

[@minerscale]

I love that someone made an implementation in Scratch of all things that's just fantastic.

[@NoNameAtAll2]

7:31 as n goes to infinity, more and more cells appear **on the inside** more and more perimeter happens within the area, which doesn't care about boundary conditions - so shape of the border stops mattering what would be interesting is to test different **distributions** of points e.g. from Bertrand's paradox

[@PurpleMindCS]

Try it!

[@Lotzerking]

Wow, great video. I would have never expected to find stochastic geometry on KZbin. I can provide some help with your problem: The asymptotic problem (n to infinity) is solved (and your "guess" of 4/sqrt(n) is correct!). For n to infinity, independently and uniformly placed points approach something called a Poisson point process. Therefore, the typical cell is very close to the typical cell of a Poisson-Voronoi diagram. The expected perimeter of a typical cell of a Poisson-Voronoi diagram is 4/sqrt(n); see, for example, Theorem 10.2.5 in "Stochastic and Integral Geometry" by Schneider and Weil. There (Theorem 10.2.4), you can also find a solution for the generalized problem in higher dimensions and different "volumes" (for example the expected number of faces or edges, or the expected surface-area in 3d, and so on) If you are interested in the finite problem, you could look up literature about Voronoi Diagrams from Binomial processes (This is the term typically used for the construction you showed).

[@drdca8263]

Oh nice! I was guessing that relating it to a Poisson point process would help, but I only got to the point of “it should probably be proportional to (1/sqrt(n))” , and was struggling to make that part rigorous (trying to relate “there are n points in this unit square” to “the number of points in a region divided by its area goes to n with probability 1 as the region is made large”)

[@ethanJ496]

Good to know! So I took a quick glance, I think the expected surface area in 3d is the "a2" for d=3 in Theorem 10.2.5? (or it could be "s", because they're the only two that scales as γ^(-2/3) .) Man, that's a surprisingly complicated expression. So, the fact that the constant "4" in the result of 2d matches a square lattice is just a coincidence? Oh, I found the definition, it's listed above Theorem 10.1.7. "s" is the mean surface area of a cell, "a2" is the mean area of a facet.

[@graf_paper]

You can feel how passionate you are about sharing the beauty and depth of mathematical thinking. Love the problem and the presentation of your ideas. Very nice!!

[@PurpleMindCS]

Thank you so much!

[@comet1072]

Hi, what a nicely made video!! A few months ago, I took a course in random geometry, where we solved problems with a similar flavor, tho we never touched problems of this level during the course. However, the techniques we covered could help you get a solution here. The main tool central in the course is called the affine Blaschke-Petkantschin formula. It seems very scary at first, but in short it is a change of order of integration (but not the any like you most likely have seen). Instead of integrating over all points in the square, you first integrate over all possible affine hyperplane (so all lines in case of the square) and then integrate over each line separately. As the boundary of a Voronoi cell is a off course (part of) a line in the square, you can see how this change of integration can simplify the integral quite a bit. I might dabble a bit in the computations tomorrow, but I definitely think it is a good approach for this problem so perhaps have a look :)) Again thank you for the nice video!

[@PurpleMindCS]

Thanks so much! Glad you enjoyed :)

[@comet1072]

@@PurpleMindCS Oki so I have some first observations: If you look up the book stochastic and integral geometry (I can't add the link, YT won't let me post the comment) and go to theorem 10.2.4 you find a result on the density of the k-skeleton of a Voronoi Tesselation in dimension d when the points are sampled through a poisson point process of intensity gamma. In short, this is the expected k-dimensional volume of a Voronoi tesselation in d dimensions in a subset of volume 1. Hence, if you plug in k=1, d=2 we get the total expected cell walls. The formula works out to 2sqrt(gamma). This agrees with your asymptotic result! Indeed, each cell wall counts towards 2 cells, and the outer square is not counted. Thus the total expected circumference equals 4sqrt(gamma) + 4. If we fill in gamma=n and divide by the expected number of n points, we obtain that the expected circumference of 1 cell equals. 4/sqrt(n) + 4/n, i.e. asymptotically 4/sqrt(n). However, there is one major issue. This solution is based on sampling a random number of points according to a PPP of intensity gamma. Of course gamma=n will be a good approximation, yet this is only an annealed result. I totally expect a quenched version of the result to hold (i.e. when we have precisely n points) at least in the limit. (excuses if I do not use quenched vs annealed correctly, I am not too familiar with the terms). Anyways, it should be doable to adapt the proof of theorem 10.2.4 to work for precisely n points. To do this, note that the proof computes the probability of a point being part of the 1-skeleton by computing the probability that a ball of a certain radius/location is void of points of the PPP (you made the same observation in your video) which comes out to e^(-gamma volume ball). If we just replace this probability by (1-area ball/area square)^(n-2), things should work, but I do not have time to crunch the numbers right now, maybe I will give it a crack later today, but I told myself to spend only 1 hour on it today :p. The proof indeed uses the Blaschke Petkanskin formula, which means that the problem of the circle only partly laying inside the square no longer is an issue. (well it is an issue, but if you follow the computations, you can see that the change of integration allows you to find ways around it). As last note: This also shows that the border of the shape does not affect the limiting behavior as long as the circumference is of order smaller than sqrt(n) (given that we assume area of the shape = 1). I hope this all makes sense, feel free to ask me some questions, I hope computations work out with precisely n points, but it will most likely be quite the headache... edit: I now see that in the proof they approach it by computing the expected density in a ball. Of course for their result, this does not affect the final answer as they use a homogeneous PPP so only the area of the shape is what matters. However, for us that means that computations might have to be quite different and we don't get the same amount of symmetries to abuse in the final steps of the proof. Maybe the computations can still be carried over to the square, but I think it will be significantly harder. Starting with a circle of volume 1 might be a better starting place...

[@homareyoshi4194]

3:40 thats so satisfying. Good editing!

[@silverstonely]

7:54 a cool thing i saw that on the square, the color shapes commonly had 4 sides, but on the hexagon most shapes had 5 sides

[@JamesThompson-c1y]

This feels like this should be easier to prove on a torus rather than an arbitrarily bounded region of the plane. That seems like the 'natural' version of this question since then you don't have to worry about the choice of the shape of the boundary. - we could also ask the same question on a sphere or a higher genus torus, but I expect we'd get different answers based on the different underlying curvatures.

[@DreamzAnimation]

my thoughts as well

[@comma_thingy]

Damn me too. That boundary was thje first thing I saw when seeing this problem

[@PurpleMindCS]

That's a really neat idea! I considered different bounding shapes but not a transformation of the space itself into something like a torus. Perhaps the issues from the bounding box go away then. I'd be fascinated to see someone code this up or try to prove something about it.

[@mistersir3020]

18:03 lol Reminds me of the following Quora question: "Murphy's law states that the best way to get the right answer on the internet is not to ask a question; it's to post the wrong answer. What are some examples where you applied this law?" Answer: "This is Cunningham's Law and not Murphy's Law. Murphy's Law is "Anything that can go wrong will go wrong".

[@AHSEN.]

5:05 hey, I know that one! Odd number of crossings means inside the shape, even crossings means you're outside :D I've used this algorithm before

[@PurpleMindCS]

Nice!

[@columbus8myhw]

Here's a good puzzle with a surprisingly simple answer. Choose four numbers at random from [0,1]. Sort them and label them a,b,c,d, so a

[@columbus8myhw]

As an extra bonus, here's a puzzle I call "the fisher and the fish." A fisher is somewhere randomly on the border of a square lake, while a fish is somewhere in the lake's interior. What is the probability that the fisher is closer to the center of the lake than the fish is? I have obtained an exact formula for this for all regular n-gon shapes of lakes. (There's a clever integral transformation that alleviates most of the pain, though I've never seen anyone other than me find it.) Strangely, for large n, this is well approximated by 6/(pi^2 n^2), though I don't know of any connection to the Basel problem.

[@fluffyllama1505]

Hmm, i tried to solve your first puzzle with a quick Excel sheet but i didn't recognize the result as anything significant (~0.68). Maybe I made a mistake?

[@columbus8myhw]

@fluffyllama1505 It should be 0.693

[@Finkelfunk]

4/√n made absolute intutitive sense to me. While all squares could be larger or smaller, given a large enough number of diagrams we will get an average that is equal in size to each of these squares with an average area. At least this is how I thought about it and it would make sense why this holds true

[@srather]

The limit for n -> ∞ should be proovable as all the edge-cases become neglegible.

[@andermium]

The submission at 17:27 seems to make a fair, but incorrect, assumption about the points being uniformly distributed on the projection along theta. Consider if theta is 1/4π, then all the points on the counterdiagonal go to the middle of the projection, but the points in the corners touched by the projection line contain exactly 1 point. The points must then not be uniformly distributed along w(theta). If you could somehow parameterise the distribution of points based on theta, or the average space between projected points, this proof technique might be the right way to get a closed form. Nice one!

[@yoavshati]

It might work better for solving this for a circle instead of a square (it's still not uniform, but the distribution should be the same for all angles)

[@karavankessel]

Yes, I originally retracted my submission for that. But then I realized that it is still okay. The average spacing is still w(theta)/sqrt(n) even if non-uniform. And it's okay if it's non-uniform because that doesn't change the fact that every single point in the square has equal chance of belonging to any one of the cells, since they are randomized! AKA The non-uniformity becomes uniform when we consider all permutations of the cell positions, and we do, since we're taking the expected value of all possibilities. Good thing too because I tried that parameterization and it was very difficult. Thanks for the comment!

[@bot24032]

Incredible. I think I want both more solvable problems and a bit of whatever this is in the future. First one for more approaches and second one for videos like this and maaaaybe for feeling of contributing to something great/less discovered like this, if i ever make it this far lol Also, criminally underrated.

[@a7medasaad549]

hi, i am not a math genues, and i don't think i can do even elemntry integration which led me to think for an intuitive way to solve it I will share what I think can lead to the solution : 1) the average parameter = the sum of all parameters / the number of shapes 2) the sum of all parameters = the parameter of the bounding square + 2* the sum of all borders length (because each border is in exactly 2 shapes) 3) the border between two shapes defines as the line passes through the middle of the two points, perpendicular on the the line between them, AND bounded by the other similar lines, or the square so which I think is important : for every pair of point shapes if we draw the perpendicular line on the line between them at the middle in the point m, and for every two or more lines intersects inside the the square : this intersection divide every line into two parts the border is the part closer to it's m. this is all what I can think of I didn't really spent time on it, this came to me from the video I don't know if this the basics every one found or I opened new path for someone, but have a nice day you all, and it was a great video

[@elunedssong8909]

Answering question at 4:30 4n/root n should be an upper bound to whatever the total perimeter is. My best explanation for why is you're creating triangles in the right picture by going from the left to the right, so total perimeter is being reduced by going from the left to the right. Also, 4n/root n was my 1 minute thinking time guess at the answer to the entire question, wonderful video so far and everything is extremely pretty!!! Edit: Pausiung again at 10:15 "Why a square's 'compactness factor'? The question is more "why don't we see very many shapes other than 4 and 5 sided shapes in a diagram?" not "Why a square's compactness factor"

[@michaelgostein]

It’s really cool to see the connection between the simple model and simulation results and those experiments in crystallography!

[@meldyluova3340]

Lets be honest, your video was so cool, awesome for your discovery my dude

[@alian714]

When I originally gave this problem a crack after watching the first video, I kept running into integrals I couldn't solve, or integrals with discontinuities and singularities - I started off with about the same idea of how to determine the average length of the perpendicular bisector between two points contained within the square - I ran into trouble with boundary conditions as well. I gave up after a few hours figuring surely my approach is just wrong. it's amazing to see just how much progress peope achieved, but wow, the fact that parameterizing the perpendicular bisector inside a square is genuinely hard is surprising

[@birbborb]

4:31 I haven’t checked if my intuition is correct, but I’d say that 4/sqrt(n) is the lower bound, as the square has the smallest perimeter for a quadrilateral of a given area; that said, maybe a hexagonal tiling would be even more efficient ? but then again the sides of the square might make it less so.

[@IamCrusaderRUS]

I'd just handwave away two things: -the boundary doesn't matter, so that we only have to deal with shapes that don't touch it. -the scale doesn't matter, so that we can lock it with something we already know: the average area of the shape. For low number of points it is in fact incorrect (thats where the bump at low number of points comes from (7:35)), but for larger number of points it is a good approximation. Then i'd rephrase the problem to "for average k-gon of area A, how its perimeter compares to the old boundary that was in its place". Not sure if its helpful, but it has some interesting stuff like how every straight line fragment of old boundary can be mapped to pair of parts of k-gon perimeter that are slightly smaller than it by a factor of 1/cos(x/2) where x is an angle between those parts of k-gon perimeter (that the same old boundary fragment happens to also bisect). Problem is, angle x affects average perimeter (of k-gon of area A).

[@gcewing]

I wonder if you could avoid having to deal with special cases at the boundary by considering an infinitely large area covered with some density of points.

[@PurpleMindCS]

This is essentially the topic of "Poisson Voronoi Tessellations" on which there are several papers. See www.tandfonline.com/doi/epdf/10.1080/01418610010032364

[@jedgrabman]

Since the square's boundary is causing so much trouble, what if you worked with an infinite plane instead? That is, instead of formulating this as a number of points in a specific square, can you reformulate it to be about the density of points in an infinite plane? I expect that the proportion of cells on the boundary of the square tends to 0 as n gets large, so almost all cells will be surrounded by other cells. For large n, I'd think the answer for the average cell boundary would be the same in a square or an infinite plane with the same average density of points. If this formulation works, it would eliminate the problems of determining when borders lie within the square and could substantially simplify solving the problem.

[@nanamacapagal8342]

Who doesn't love proof by community effort?

[@davidawakim5473]

Great content, you're an amazing scholar and I wish you the best of fortunes in your future endeavors sir

[@PurpleMindCS]

Thanks a lot! Much appreciated.

[@empireempire3545]

Regardin the Voronoi diagrams, i have a problem for You that i've been struggling with for some time: a distribution of points on a surface and their corresponding voronoi diagram is given. Then, all the points are moved slightly (adjustable parameter during the simulation to keep the stability) according to some arbitrary rules. How to adjust the voronoi diagram so that it fits the new positions? The idea is to NOT recompute the new diagram from scratch every time the points are moved - the points will be moved at least hundreds of millions of times so we have to make the calculation as efficient as possible.

[@DeadJDona]

well try to recalculate few thousands, and calculate the diff to see patterns

[@drdca8263]

For small changes in the points, whether two cells share a boundary is unlikely to change… For how the boundaries change.. Well, (1/2)(p_1 + p_2) + t RotateNinetyDegrees(p_2 - p_1) this is linear in p_1, p_2 . Now, for the endpoints of these, the boundary values for t, this will most of the time, for small changes in the positions, be meeting the same cells at the endpoints.. So, I guess, ah, well, the distance between the midpoint and the point along the perpendicular bisector is given by |t| times the distance between p_1 and p_2 , while the distance between the point along the bisector and the point in the third cell… there’s the distance from the midpoint to the center of the third cell, and there’s the angle made between the bisector line and the line from midpoint to center point of third cell, and those should give you how far t can go. Though, ah… That seems a bit redundant dealing with each corner multiple times. How are you representing the Voronoi diagram? Maybe by the vertices that the edges connect? I think generally each of them should be at the corner of exactly 3 cells… Ah, hm. Well, if you get the perpendicular bisectors for 2 of the pairs of sites, then to compute where they intersect

[@drdca8263]

Ok, found something: the vertices where the edges of the Voronoi diagram meet, if there are 3 cells meeting there, can be obtained as the circumcenter of the triangle whose 3 corners are the centers of the 3 cells. Wikipedia has a formula that gives the circumcenter in Cartesian coordinates, in terms of two 3x3 determinants, and also computing a norm^2 of each of the sites. So, computing the new norm^2 for each of the sites, and then for each vertex in the diagram, do like, 12 multiplications (none of which depend on each-other) and 12 additions or subtractions. If you are ok with approximations, you may be able to skip computing the norm^2 values on some of the steps?

[@silverstonely]

5:07 an irregular heptagon with an orange dot moving across it

[@FernTheRobot]

4:30 my guess is that since the area is the same, this question can be intuit as "if a random polygon has the same area as the square, would its perimeter be bigger or smaller than the square?" My intuition tells me a site will have about 5-7 neighbors, making it a 5, 6, or 7-gon. I would say a random n-gon is on average closer to a circle and have less perimeter to area ratio than a random m-gon where m < n. Therefore the square grid site situation is an overestimate of the total perimeter. Now onward with the video and see if my intuition is correct!

[@yktserea2214]

I’ve been thinking about this for months now, I think there’s a lot more to it than ppl think

[@gramagon3680]

Really loved trying this problem. Looking forward to the next video!

[@PurpleMindCS]

Thanks so much! Happy to see your continued engagement :)

[@TheNameOfJesus]

Sometimes the simplest way to solve a problem is to change the problem. In this case, I would change the problem from a finite flat square to a finite sphere. This will eliminate many or all of your edge cases (pun intended.) Maybe try this idea.

[@alclelalclel]

7:07 squaring the circle reference

[@Cammymoop]

Initial guess: It seems like the regular square grid might represent an upper bound for the average perimeter, i noticed the example of throwing all the points in one corner actually minimizes the total sum of perimiters while giving almost all of the printer to only one point. So it feels like keeping the regions equal in size will represent the other extreme.

[@soren81]

Having not studied this at all, I would assume that the total perimeter would be related to the length of the edges in the delaunay triangulation, which is the dual of the voronoi diagram. The total length of the triangulation should be a lot easier to calculate.

[@rubiksmath7938]

This is cool - I’d really really *really* like to see the methods and thought process behind some of the viewer submissions, it would be such a rich learning experience. Excerpts in the video here are such an appetiser for wanting to read more - are they in the discord or available elsewhere?

[@PurpleMindCS]

Hey, so glad you enjoyed! While these videos are more of a summary of many different viewers' approaches and it's not possible for me to include a fully-detailed description of each thought process, you may be able to find more of what you're looking for in my Discord server. Scroll through the recent-videos-discussion channel and you should be able to see the history of people working on this problem and also the problems from previous Brainstorm episodes. I'm sure many of them would be happy to talk to you about it as well!

[@iamsushi1056]

The problem is intuitive but at the same time oh so so mind bending

[@edwardhunia6315]

I'm already working on my own stuff, so I'm not interested in doing a proof. However, I have sketched an outline of a potential approach: 1) Conjecture: The square represents the upper bound of the maximum perimeter for any given finite area of a Voronoi cell given a limited set of sides. Is this true? 2) Conjecture: Add to the set of square Voronoi cells the sum of 𝑛 Voronoi cells, each with perimeter 𝑝, to give a lower bound area with the increased complexity of sides. 3) Conjecture: As 𝑛 approaches infinity, this sum converges to the upper bound. We can intuitively know this because we get zero area Voronoi cells. Is this true? Challenge: Determine if the limit case is general enough such that the lower bound equals the upper bound for all 𝑛.

[@Uri131]

Assuming uniform distribution, the mean distance between points is 4/sqrt(n). I would look for a mapping from the distances to the perimeters that preserves this quality

[@billcochran1628]

Good luck using the medial axis to solve a Voronoi diagram problem. I squeaked out a Voronoi diagram solution to a medial axis problem once.

[@billcochran1628]

You are trying to solve edge detection and propogation in PDEs, you just don't see it yet. The medial axis and the VD are duals, so any computation that limits one, limits the other. in this case, you are trying to propagate a hard edge in a conservative field in the world of medial axes. at least, the math you would like to write down, would solve that problem. this, as far as i am aware of, can only be simulated.

[@davidmurphy563]

0:36 Stopping here. I'm reasonably familiar with voronoi. Coded them from scratch, used them a bunch of times. The issue here is you asked the question without first answering the "who cares" question. Always answer the "who cares" first. Because otherwise, who cares?

[@Ibuiltatower]

I don't know if this is a useful angle (hah) to take, but if I were to try and work this through, I would consider whether/how using different metrics on the space would change the answer. For example, if we construct our diagram in the L¹ metric, what does that do to the perimeter? Then do the same in the L³, L⁴, etc. metrics, even if we're only working on the level of computed approximations to the true average perimeter. It seems to me that justifying the "Approximate the diagram using a square lattice" approach would be much easy if we're constructing our diagram in L¹ (even if we're not necessarily measuring our perimeter in L¹); if we can find a rigorous proof of a result using that approach in that metric, it feels reasonable that it might guide us in finding a similar result in other Lp metrics.

[@N-pm3lg]

I had no clue whatsoever how to tackle this one

[@Avorthoren]

2:18: no, you can't expect the average area of one cell to be 1/n, because cells on the edge are not equivalent to cells in the middle. Maybe when n -> inf you'll get there... Anyway, it at least requires more explanations and proof.

[@ИльяСтрелец-ц4к]

14:05 Could we really say that average perimeter with other cells is a sum of average of border length? Shouldn't borders lengths be independent for us to say so?

[@Nworthholf]

4:29 - I'd guess that the closer your random is to true uniformity, the closer it will be?

[@DeadJDona]

4:00 is it even possible to create perfectly squared voronoi?

[@BleachWizz]

4:35 - the first thing i'd check is if that's not the exact answer... because the average of the average is the average, so... the grid distribution should average the distribution of perimeter across all squares and that should represent the average of perimeters, but double average cancel out to a single average so there should be a high probability that's just it and you do have the answer.

[@drdca8263]

0:36 : ok, idea: consider rather than having a 1 by 1 square and placing n random points on it selected uniformly and independently, we instead consider randomly placing points on the entire 2D plane with a particular density (so that for any rectangular region, the distribution of the number of points placed in that region is given by the Poisson distribution with parameter the density times the area of the rectangular region). We can still take the Voronoi diagram for the infinite plane this way, and we can consider the perimeter of the Voronoi cell containing the origin (the distribution of how the points are placed is translation invariant, so picking the origin like this doesn’t matter.) The distribution we get over the set of points if we draw one sample (of infinity many points) from the starting distribution, and then scale the set of points by some factor (like, scaling by multiplying each point by the factor, so scaling how far away it is from the origin), is the same as the distribution we get if we instead scale the density by the square of that factor. When we scale the set of points by some factor, the corresponding Voronoi diagram, and all of its cells, is scaled by the same factor. In particular, the perimeter of the Voronoi cell containing the origin will be scaled by this factor. (Its area will be scaled by the square of this factor.) So, scaling the size of everything by r scales the perimeter by r, and scales the density by r^2. So, scaling the density by n, scales the perimeter by sqrt(n). Of course, if we pick a particular 1 by 1 square, the actual number of points in that square is not necessarily equal to the density (the density needn’t even be an integer, after all.) But, if we take larger and larger finite convex regions, and select a random 1 by 1 square within that region, on average the number of points in the square will be equal to the density, and the variance should decrease. Uhh… I want to get something like, E[perimeter of cell containing origin|density = d] = E[perimeter of cell containing origin | “there are exactly d sites in the square”] (where quotation marks here are indicating something that doesn’t quite make literal sense) When n is large at least, the effects from the edge of the square should be negligible because the chance that the randomly selected Voronoi cell will be one of the ones that touches the boundary, should be negligible. Is there a good way to figure out the proportionality constant..? Ah! If we go back to thinking about the case where we hold density constant and then scale things, we can look at like, squares containing the origin and which have the desired number of sites in them, and then scale them (and the points in them) down to get a unit square… Hm. In that case, we get some joint distribution of densities and perimeter of the cell containing the origin, depending on the number of points required to be in the box. Conditional on the density we have the expectation of the perimeter (up to a proportionality constant)..

[@drdca8263]

E[perimeter | n in box] = \int E[perimiter | density = ho] * p(density = ho| n in box) d rho Uh, P(n in box | density = rho) = exp(-rho) rho^n / n! uhh… if we have density 1, and we have that in some box we have m sites, then the probability that after making the box bigger to increase its area by A, that it contains no additional points, is exp(-1 A) A^0/0! = exp(-A) . Uhh… Hm. Ok, I give up. I’ll watch the rest of the video now.

[@drdca8263]

0:52 : oh, ok, I guess the video probably won’t have a full solution? Maybe I’ll try more after watching.

[@drdca8263]

4:32 : “do you think it is greater or less than 4/sqrt(n) ?” : low confidence guess: less Reasoning: they look closer to circles than squares, and for a circle and square of equal area, the perimeter of the square is 4/pi times the perimeter of the circle Edit: what I said in this comment made no sense. If a circle has area A, its perimeter is 2 pi (sqrt(A/pi)) = 2 sqrt(pi) A , And if a square has area A, it has perimeter 4 sqrt(A) . So, the ratio would be 4/(2 sqrt(pi)) not 4/pi

[@drdca8263]

7:00 : ok, so it was more, but only slightly. Huh.

[@drdca8263]

12:49 : ooh! This seems like a case where the infinite volume case could be nicer! Because, we wouldn’t need to cut out a portion of the circle. Assuming the kind of process I mentioned before, for a density rho and an area A, the probability that no sites are chosen within a chosen region which has area A, is exp(- rho A) .

[@askcaralice]

17:10 ramanujan joined the chat

[@loseControlGD]

Ok, W for whoever made it in Scratch...

[@Nathangallagher]

I would have gone with a very different approach inspired by kzbin.info/www/bejne/l16aZ2qNo8eUebM Where instead of randomly sampling points within a square to randomly distribute points on an infinite grid and to randomly place a square onto the grid. If we have such a random distribution where the density of points is one per unit area and we define P as the average perimeter of all voronoi cells, we can then randomly place a square of side length N on the grid. This square has an area of N^2 and so has on average N^2 points by the density we chose. The sum of all perimeters of all voronoi cells within this square, denoted as S, is approximately equal to PN^2. (It is not exact as any voronoi cell on the boundary of the square will have its perimeter modified but as N grows this will have no effect as this only happens on boundary cells whose contribution scales linearly compared to the quadratic growth of PN^2) To replicate the original question choose a square of side length sqrt(N) to have a square with N points with S = PN. Then scale the whole square by a factor of sqrt(N) to get a square of side length 1 with N points and S = P*sqrt(N). (Both N and S are lengths so we scale both by a factor of sqrt(N)) So P*sqrt(N) is the sum of areas of voronoi cells so we divide by N to get the average of P/sqrt(N) If we can now calculate P=4 we can prove the result in the video and I believe we can do so using the integral defined in the video, by calculating P before adding the square boundary we avoid having to calculate the intersection of a square and a circle. Also this works with any shape with the correct area as your results also expect. I believe we can construct the random distribution of points with something called the poisson point process or Complete spatial randomness. en.wikipedia.org/wiki/Poisson_point_process#Generalizations en.wikipedia.org/wiki/Complete_spatial_randomness (I literally just googled this and did this math now so it could all be wrong). With this you choose some value L as the density of points and can define a process such that for any measurable subset B of the space, the number of points within B, denoted N(B) is given by P{N((B) = n} = ( ((L|B|)^n)/n! )e^(L|B|) Where |B| is the area of B In other words the probability that there exists no points in B is e^(L|B|). By using the method you showed at 12:00, we take two points, a and b, on the plane and define the perpendicular bisector of them and map it the the real line in the obvious way where the midpoint of a and b is mapped to 0. We can then create a function on R such that f(x) is the probability that x is on the boundary of cells a and b. Which is equivalent to the probability of there existing no point in the circle centered at x that touches a and b. The probability of this is given in the formula above so we only need to parameterize the radius of the circle. First we know that L = 1 as this is value directly corresponds to density. To find the average distance between a and b we will assume that they are "neighboring" points and that "non-neighboring" points have a boundary of length 0. The page en.wikipedia.org/wiki/Complete_spatial_randomness#Distribution outlines how to find the expected distance between a and b assuming they are neighbors by "use of the gamma function using statistical moments". (Again i just googled this topic so i didn't do all the math) With this you can calculate the expected distance between the points a and b, with the points on their perpendicular bisector and hence the area of the corresponding circle and therefore the probability that a given point is on the boundary of a and b. From here you need to somehow turn this probability distribution function into an expected length of this boundary, which if i interpreted the video correctly is a method to solve the central part of the integral at 14:22. This approach may work if someone else wants to look into it but it may also be flawed as I just researched the topic and am not very good with statistics at all.

[@BenAlternate-zf9nr]

Could you get an exact answer for a given density of nodes in an infinite plane?

[@PurpleMindCS]

I believe this is the focus of several papers -- search "Poisson Voronoi tessellation" on Google Scholar and you should find a lot of information about that. Here's one: www.tandfonline.com/doi/epdf/10.1080/01418610010032364?needAccess=true

[@Crayonberry1212]

1953 is not "almost 100 years ago" 😆

[@PurpleMindCS]

The original paper by Scheil and Wurst was from 1936. Although maybe I could've worded that part a bit better :)

[@NinjaOfLU]

Side thought: is there an alternative distance 'metric' which makes some of these perimeters nicer? I'm looking at the argument at the start, and noting that max(x,y) _does_ remain constant with angle, and we know that's strictly less than the Euclidean distance, so I wonder if could abstract away some geometry into a bound, using that... And another thought. Some of the issues here arose due to intersections with the edges of the square. What happens if you do this in a space with some different topology; say a periodic space? Actually... In a periodic space you might be able to get some interesting self-similarity results.

[@Phlosioneer]

Can we get a bit of an easier problem next time? Not asking for much easier, but like, getting anywhere with this required either programming a simulation or being comfortable with line integrals over an unparameterizable line. It looks easy as symbols animated in a video but working with something that you know is incalculable is usually a sign of a dead end, not a sign of progress.

[@tylerduncan5908]

Is it possible to use a method that assumes a large n and start with a region that, when removed, leaves an area that's congruent to the original. Then you could delete an individual region based on a clever algorithm, and then scale up the remaining portion to fill the original area and repeat until we have only 1 region left? From that point, it's only a matter of proving that any diagram with a region removed has a sufficiently similar total perimeter to the original, and of course you would probably need to show that average perimeter is invariant for all starting shapes. Idk if any of that makes sense, i am spitballing completely and could be talking out of my ass, but that would be my initial approach.

[@obiwanpez]

Noice. We learned about Voronoi Diagrams in Neural Networks.

[@obiwanpez]

6:40 - Would you say that the math is… unreasonably effective?

[@sergejnekrasov7688]

Isn't it necessary to specify at one points how random the sites really are, i.e., from which distribution they are drawn?

[@donaldhobson8873]

I think 4/sqrt(n) is asymptotically correct for large n, because I did the integral a while ago.

[@AFufn]

No way its solved

[@williamnathanael412]

I thought you were going to show the Four Color Theorem!

[@PurpleMindCS]

Maybe I should've applied it to the diagrams just for fun lol

[@deinauge7894]

If you are only interested in the n->infinity case, you can ignore the border of the square and pretend that the whole plane is covered with a density of n points per unit square. Here is my short "proof scetch" that can be made rigorous without too much work: Your integrand simplifies to exp(-pi n (r^2 + (dx/2)^2 + (dy/2)^2)) where dx and dy are the difference between the points. (why? Because the area where no other point shall be is A = pi (r^2 + (dx/2)^2 + (dy/2)^2) and therefore you expect n*A points inside. The chance to find no point is exp(-ExpectedNumber)) Integration over r is simple, and you are left with exp(-pi n ((dx/2)^2 + (dy/2)^2))/sqrt(n) With the same argument, that the border effects go to 0 at n->inf, fix one point and integrate over the other from -inf to +inf. The chance of getting contribution outside the square vanishes for large n. In the end, the integral is 4/sqrt(n)^3 inserting into your formula for the average perimeter: 4/n + (n-1) 4/sqrt(n)^3 ~ 4/sqrt(n) as n->infinity

[@deinauge7894]

Please correct me if I'm wrong, that's what came out of my head on the fly while writing the comment 😅

[@saltylizard]

7:10 good luck doing that

[@aloysiuskurnia7643]

Sigh here we go again... *Whips out the spiral of archimedes

[@zacharychase7652]

I'm confused. Do you guys expect 4/sqrt{n} to be the exact answer? If so, what is the screenshot shown at 17:17 about?

[@columbus8myhw]

Would you like to hear about what I call "the biggest hermit problem"?

[@PurpleMindCS]

Saw your post in Discord :)

[@ЕрденХакимжан]

Hey! What about another dimension? Would it be 6/n^2/3? Maybe for m dimensions it’s (2m)/n^(m-1/m)?

[@burrdid]

this is so weird because i have something that look very similar in scratch. points closer to sites are colored the site color but didnt do any perimeter calculations

[@MrBmarcika]

The integrand is zero, since a finite union of line segments has measure zero in the unit square no?

[@Makememesandmore]

I wonder why it puzzled everyone you showed it to

[@ralvarezb78]

May be use Green's identity to estimate the probability ?

[@Nnm26]

You can’t prove it because it’s not 4/sqrt(n). It’s 2*sqrt(pi)/sqrt(n) as n tends to infinity

[@Nnm26]

Approximately, the actual value is like 3.57 if my simulation runs correctly

[@iwersonsch5131]

Oh the perimeter? I was solving for the area, lemme rewatch Edit: Ah indeed, you talked about using an amount of paint (area) but then said perimeter in the final question. That did stump me, my bad

[@pakumenbutts5942]

I am completely unsurprised to see a SM64 ABC person on a video like this

[@lionel4685]

I'll give it a try, but my math skills are very rusty, so there is nothing very rigorous here. I would love if someone would review it and maybe calculate the solution, which I can't. But it goes like this : Let's draw a square grid of size e, e will tend to 0. What we are looking for will be the number of squares of that grid that are crossed by some cell perimeter line (let's call this number G(e)). We can do this because we are looking for an average and not an exact value, but we will have to adjust the result with the average length of a line crossing a square, at any entry point and angle (lets call this t(e)). We'll work with a infinite plane full of.cells, considering only a square region of side L with n points (cells) inside. The density of the cell centers inside the grid is d(e) = n*e^2/L^2. It's also the probability that a square of a grid contains a cell center. We'll note that a point of a plane will be on a cell perimeter if and only if the two nearest cell centres are at the same distance from it. We'll call r the distance to the nearest point, then we are looking for the probability that the circle of radius r centered on the point we are considering contains at least 2 points. Now considering the grid, para calcular G(e), we just need to consider these three things, which all should be possible to calculate : - the average value for r - the number pr(e) of squares crossed by the circle of radius r average - the number ar(e) of squares inside of the disc of radius r average (perimeter excluded) If we would look for only one point, the probability might be something like d(e) * pr(e) + (1-d(e)) * ar(e), but for 2 points or more I am not sure. The solution to the problem would then be something like : [ lim(e->0) G(e) * (L/e)^2 * t(e) ] / n * 2

[@atavoidirc5409]

13:57 isn't this 4/(4(n-sqrt(n))+1)

[@JKyLE456]

1953 was not "almost a hundred years ago" 😭

[@PurpleMindCS]

But 1936 is! That's when the original paper by Scheil and Wurst was published.

[@pedrogarcia8706]

Bad news bub

[@pi_ist_toll]

Small question: which program do you use for your animations?

[@bloom945]

manim, says in the description

[@pi_ist_toll]

@bloom945 damn read almost everything of the description. thanks anyways!

[@thomasreparat8487]

Has the percentage of the circle outisde the square problem been solved or not

[@rrock2025]

That's cool....................................................

[@qovro]

Is there an approximate answer for the 3D version of this?

[@danielgostein3039]

As in the surface area of the boundary?

[@PurpleMindCS]

Good question! This is actually covered in the paper I referenced by Meijering (check the description for the link). He starts off that section (page 218 of the paper) with a mathematical analysis of the 3D version, calculating expected values for the surface areas of boundaries between crystals in different models including the "cell"/Voronoi model, and Johnson-Mehl model.

[@teamredstudio7012]

these are like 3blue1brown video's

[@nakulpatel3711]

Is it really unsolved problem like reimann hypothesis? (Please enlighten me😅)

[@donaldhobson8873]

There are a lot of not-famous unsolved maths problems. They only get famous when lots of mathmaticians try and fail, and the problem is particularly interesting.

[@ciCCapROSTi]

It would have been nice if you define what you mean function, because I after posing the question I still have no idea what you and your viewers searched answer for.

[@MihaiNicaMath]

Nice video! In my latest video on my channel, I found an approximation for the sum of powers (e.g. 1^m + 2^m + ... +n^m) exactly by doing the relate to an expected method you described at 16:39

[@PurpleMindCS]

Ooh, cool!

[@prodcio]

[@FinleyRichardson-tk7cv]

Try it in 3-d

[@Arsenniy]

wow

[@riotcelestian4587]

I'm waiting.

[@NoName-qf7lu]

Same

[@elfeiin]

I really hate videos like this where they show something cool and then don't show uses for it. BOOO!

[@drdca8263]

He showed an application of it in describing the grain structures of metal things?