Hey guys! I recently made an online store with a few fun little things. Let me know if there's anything else you'd like to see on here :) purplemindcs.myshopify.com/

The reason you can rule out galactic algorithms from practical use is that it’s obvious that they can’t be used. To represent a number by digits, every digit has to be represented by something. At best, a single particle can represent a few (thousand) digits. If you consider the amount of particles in the whole (observable) universe, they’re simply not enough, not even close.

This shit ain't surprising at all bro. The moment I hear "[name] diagram" I'm out of my league.

At 7:43, the kink between blue and light blue in the octagon is a glitch, right?

How do you choose a random zero dimensional point in a continuous plane?

Where’s Cleo when you need her? 😅😂

7:10 Ancient Greek watching this video : *jaw drops to the ground*

will make sure participate in the next one!

9:57 this is a bit more important then a throw away comment

dis bc u got shit explanation about creating shapes of sites around dots. will not even whatch now

Proof by not

The tangent space of the functions forms 1/4 of 2pi for 90 degrees with an intersect of one half the space for tangent 45 degrees as tangent +/-1 (+1 for 45 or 225 degrees, -1 for 135 or 315 degrees). Let X be Sine from 0 degrees to 90 degrees; Let Y be Cosine from 90 degree to 0 degrees; When 1/3 of the tangent space, sin(30)=cos(60)=0.5; When 3/3 of the tangent space, sine(90)=cos(0)=1; When 2/3 of the tangent space, the sine and cosine meet at the tangent of 1 as sin(45)×cos(45)=0.5; The vectors movement through 90 degrees in 1/3 movements resolves to [0.00,0.50,0.86,1.00] where each 1/3 movement is equivalent to the 0.5 for 3×0.5=1.5 and a loss where the sine and cosine meet as the `sin(45)×cos(45)=0.5` for 1.5-0.5=1.0 as thr integral in Crofton's formula.

I really like how your channel inspires the viewers to actually try to figure out things on their own. The brainstorms are amazingly cool, and I hope you keep doing those on wider areas than just probability, I think it'd be awesome.

How about the quick inverse root algoritm. I think that more people should about it bc it's cool

i have been humbled :(

Voroni is dual of Delauney triangulation. so, let's start with perimeter of Delauney, and this time it is easy because we are dealing with just triangles. Then, as a dual graph it is possible to show that perimeter of voronoi cells are smaller than perimeters of the triangulation. So, a limit easily appears.

Intuitively, the bounding shape should not matter(*), because as n becomes large, a negligible proportion of cells touches it, and the vast majority is in the bulk. Then the only thing that counts is the density of the cells. Right? *: as long as the bounding shape isn't some fractal or so...

1:58 the first 6 digits of pi and e

Consider the plane R^2 with the random distribution of point of density 1. We can show that the number N of points in a subset S of R^2 of area A is a poisson random variables : P(N=k) = A^k/k!*exp(-A). We want to compute the expected value of the length of the median which is in a Voronoï cell between two points at distance d of eachother. As it is stated in your video, a point p is on the Voronoï cell if no other points in the circle of center this point and radius distance to a or b. Let x be the distance between p and the midpoint of a and b. So this probability is P(N(circle)=0)=exp(-pi*(d^2/4+x^2)) We integrate this over x to get the expected length : we get exp(-pi/4*d^2). Finally to get the mean perimeter of one Voronoi cell we integrate this over the whole plane : \Int_0^\infty Exp(-pi/4*d^2) * r * dr which is 4. So we have that the mean perimeter of a Voronoï cell on R^2 with point density 1 is 4. If we increase the density to sqrt(n) so that there are on average n points in each unit square, so we get that the average perimeter is 4/sqrt(n). The case of n points in a unit square should give the same result because as n goes to infinity the proportion of Voronoi cells touching the square is null compared to the interior Voronoï cells.

A ≥ 4

Have you tried simplifying the problem to a more general thing. I think you could definitely prove that as you have a larger N, the less the shape of the container matters, so you could just find the aproximation of either a circular container (matters less to consider the many varieties of conditions) or even an infinite container, and just assume some uniform density of voronoi points. And that way you should have a much easier way figuring out the integral

Very enjoyable and well-done. I really enjoyed the animations; eye-catching without being too distracting. Immediate 'subscribe' about three minutes in!

Maybe it is helpful to think about the related problem for the whole plane with an average of n points within any set with area 1. Then one wouldnt encounter a boundary that restricts the circle. That may be especially interesting for the limit as n goes to infinity, as the perimeter of the square as a fraction of the whole perimeter goes to zero. So one should atleast from my first impression get the same answer as for the whole plane. One might have to exclude cases in which the boundary between 2 points is infinite, but that might be no problem, as the probability for that happening seems to be 0 to me.

I am not sure, if we can that easily just integrate over the probability of a point on the perpendicular bisector being on the border between two cells, because the probability of points on the bisector being on the border is not independent. For example, if you know that points x and z lying on the perpendicular bisector are part of that border, you also know immeadiately for any point y between x and z, that it lies on the border. Maybe, that doesnt matter in this case, but i would have assumed one had to do something more like a double integral over the perpendicular bisector using the probability density of the two points forming the boundary of border multiplied by the distance between these points. I am not sure though. And maybe both these methods actually yield the same result. But great video. Very interesting. I specifically loved the way of engagement with the viewers and their input.

I once had a college Project to write a program in Pascal to multiply large numbers. It was pretty insane. This was back in the late 80's.

The combination of clarity of explanation, high production values, and making a challenging subject approachable in this video are exceptional. 3blue1brown level content with 14k subscribers - deeply impressed. Thank you.

as someone who uses voronoi cells as "base" for a lot of my fantasy/roleplay mapping: this is actually a really nice and useful result, even if it's "only" empirical!

This is the first computational complexity video I’ve seen that clearly explains that it’s about how it increases with increasing size of input! (You’d be surprised how often this is implied or skipped over)

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

Your viewers are gold

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

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.

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

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

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

omg the voice crack at 19:29 was tragic 😭

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

Try it in 3-d

You can also use different sided dice if the number of combinations is the same. For example, you could swap 2d6 for d4,d9 with the sides [1,2,2,3],[1,3,3,5,5,5,7,7,9]. Or 3d4 could become 2d8 with sides [1,2,2,3,3,4,4,5],[2,3,4,4,5,5,6,7]. 2d8 could become 3d4 with sides [1,2,2,3],[1,3,3,5],[0,4,4,8] (yes, you need to allow 0 to make that conversion, but a zero-face die is valid enough. Just not so useful for rearrangements when you're keeping the number of faces on each die the same as it typically just shifts one pip from each face of one die to the other).