Can You Solve This Geometric Puzzle?

This is episode 3 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 second part, I follow up with animated discussions of the solutions that were sent to me, along with my own solution.
You can check out the latest follow-up episodes here:

This one is about a certain randomized iterative process that one can use to create a very pretty geometric construct called a Voronoi Diagram (named after Georgy Voronoi).

Have fun, and I look forward to seeing what you all come up with!

These animations are made using Manim, by 3Blue1Brown.

[SpencerTwiddy]

Now we’re just doing homework on our own… what is wrong with us!

[scoffpickle]

In the diagrams, straight up puzzling it, and by it, heh, let's just say... my Voronoi 😈

[CananaMan]

instant subscribe!!! I've been looking for a math problem channel that doesn't give the answer away immediately and encourages viewer participation :)

[miguelanjo]

fully by vibes, i think the harmonic series is gonna get involved

[Thavleifrim]

Without putting to much effort into it this sounds like a harmonic series in disguise, so probably alot of paint.

[DWal]

the difficulty curve on these go crazy.
for anyone actually interested in solving it, maybe start with finding the upper bound on perimeters? arranging the site points along a regular polygon's vertices comes to mind

[hughobyrne]

Conjecture: the more points there already are, the more the shape defined by a new point resembles a circle.

[draidog]

very projecteuler, kudos for the nice problem!

[ccolombe]

Love the hard and interesting math puzzles! Keep em coming :)

[dirkroosendaal]

this is so sick. I love this concept omg. I am not smart enough if to submit it, but if i find the idea, i will defenitly submit. and if not, then i wait on other peopels repsonsen.
Now that that has been said, i need to rewatch the video again to really understand the question.

[donaldhobson]

The average area is 1/n=pi*r^2, so a lower bound on average perimeter is 2*pi*r=2 *sqrt(pi/n)

[Negreb]

This seems like the hardest puzzle yet

[francomiranda]

Cool problem, at the very least its led me to discover that a guy named Fortune was able to make a sweeping voronoi algorithm in the 80's and that minds greater than my own w're able to implement it in javascript in the 2010's!

I intend on trying to approximate through simulation, but given the nature of the problem it would seem that a key insight is that E(n) = E(n-1) + F(n), where F(n) is presumably some decreasing function since new cells should get smaller on average as n grows.

I guess the meat of the question, then, lies in finding this F(x)

[BrianSpurrier]

A detail that I think will be very useful is the fact that if you reordered the points, the expected total perimeter should be the same, since they are randomly distributed

[openendings]

Conjecture: the border between A and B's cell, if it exists, is framed by the cells for C and D such that ACBD is a convex quadrilateral with the largest possible angles DAC and CBD.
(In the extreme case, when the cells barely touch, it's a cyclic quadrilateral.)

[Thmsdu]

Ok, I think I got it (somewhat)
Let's consider the total length of the outer edges (4), and the total length of the inner edges (F(n)). The question is to find the expected value of 4/n + F(n)/n.

Let's, for some integer m, divide the square in m^2 small squares. If n is big enough, each square contains n/m^2 points, and a total length of F(n/m^2)*1/m inner edges (the 1/m is a scaling factor). Thus F(n) ~ m*F(n/m^2). Thus I believe that F(n) ~ \sqrt{n}. Thus the sequence would be 4/n + K/\sqrt{n} + o(1/\sqrt{n})

[bearantarctic]

Lmao, what happened to "I'm not quite sure about the third episode right now"?
I'm glad that you did release a third episode! I'm going to start working on it soon

[johnchessant]

question: is there a reason you ask for the expected perimeter sum, rather than area sum?

[joshuasims]

Huh, curious! The puzzle and solution type feels very Project Euler. I find the freezeframe at 1:52 explains the challenge best!

[korayacar]

My guess is that the answer is O(sqrt(n)), and more specifically 8*sqrt(n) + O(log(n)), and here's why:

Consider the perimeter around the last site to be added before and after a diagram is uniformly scaled by a factor of 2, and the region around a unit square containing the site is removed. The perimeter around the last site is scaled by a factor of 2, whereas the number of points in the resulting diagram are cut down by a factor of 4, suggesting an inverse square relationship between the perimeter of the last site and the number of points.

Taking this relationship as a given, an estimate for the sum of the perimeters in a diagram with n points would be the perimeter of the unit square times the sum over the inverse square roots of the integers from 1 to n, which can be bounded above and below by 8*sqrt(n) +/- the sum over the reciprocals of the integers from 1 to n.
All of this means that the solution should be O(sqrt(n)), and if the above estimation is accurate, 8*sqrt(n) + O(log(n)).