Here’s something fun I was playing around with today. I generated 100 random points and connected some of them with lines. Can you figure out how I chose which lines to draw?

How about these? (Same points, different lines.)

Or these?

Here are some more. The first three groups in the grid below correspond to the pictures already shown above.

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Draw a line to your closest neighbor, 2nd closest neighbor, et c.

Hmmm… For the first one, you calculated the nearest neighbor distance, sorted by ascending distance, connected them one at a time in that order until each point was connected to at least one other point.

For the next one, you calculated the 2nd nearest neighbor distance, sorted by ascending distance, etc.

Same for the nth group in the grid (L-to-R, T-to-B).

My guess is that in the first picture each dot is connected to the dot closest to it, the second picture is each connected to the second-closest, and so on.

Right! The only thing that’s not quite accurate is Devin’s comment “Same for the nth group in the grid (L-to-R, T-to-B).” Look more carefully… =)

This was fun for me since I actually had no very good idea of how it would look before I tried it. It’s interesting that with connecting nearest neighbors you end up with lots of small connected structures. I wonder — what is the expected number of points in one of those connected structures?

[squint] Perhaps the second row isn’t 5th-closest neighbor? Maybe the 11th closest? In which case the next rows are 21st and 31st? Great fun!

Something like that. I don’t remember the exact numbers I used. Note, however, that the final one corresponds to the 100th closest (or maybe 95th, something close to that anyway)—all the edges go diagonally to the furthest corner.

In effects for movies, these connection tricks are used all the time. For instance in particle simulations points will move around based on some dynamics and then turned into a volume by connecting n-closest with segments. It’s sometimes easier to design the effect and visualize the end result than moving around volumes. plenty of examples here: http://www.imdb.com/video/imdb/vi3445005593/

not a great movie though.

Cool, didn’t know that!

I will admit that I had absolutely no idea about your reasoning for building the connections that you did, but after reading the comments above, I finally get it.

That’s a very interesting subject! I coded it and started to play with it: there are many phenomena worth studying. For example, the total number of lines seems to peak at the 55th neighbour with more than 99 lines. For comparison, it only reaches 69 in the first neighbour case. I guess this could be derived rigorously by computing the probability that two nodes are mutually their kth nearest-neighbour.

It would be worth computing the modularity of the graphs or other such measures…

However, when you reach the 99-100th nearest-neighbour, the 4 angles attract pretty much all the lines. A version avoiding this would consist in taking a uniform circle for the positions of dots.