Socks: Designed With Maths

This blog is one of a series that originated from our Lunch and Learn sessions at Fuzzy Labs. An opportunity for us to share interesting topics, practice our public speaking and have a nice lunch together!

Without further ado, let’s jump into it. Today’s blog is all about socks, yes, you read that right, socks.  But these aren’t just any socks, these socks are designed using maths. Specifically a mathematical pattern conceived by the Russian mathematician - Voronoi. Danny had the idea for a cool bit of merch for our LLM hackathon last year.

You can find the code for everything discussed in this blog here: https://github.com/EchoStatements/Voronoi-Generator

Voronoi Diagrams

Voronoi diagrams are surprisingly common in nature, you’ll see them in the coat pattern of a giraffe or the cracked surface of dry mud. To put it simply, they are simple polygons with interesting properties and they also have a wide range of applications, from cartography and biology to computer science and art.

Voronoi Diagrams are a natural way to divide space into regions. Chances are you’ve encountered them countless times without realising it.

What Makes a Voronoi Diagram?

To understand how we go from plain white socks to the final product, we first need to understand how Voronoi diagrams are created.

Let’s start with a simple example:

Imagine you have a few spots marked on a piece of paper. A Voronoi diagram is a way of dividing the paper into different zones, one for each spot.

Each zone contains all the places that are closest to its spot compared to any other spot. If you pick any point inside a zone, the nearest spot will always be the one that "owns" that zone. No matter where you move within a zone, you'll never be closer to any other spot than the one that defines it.

If you're interested in the mathematics behind Voronoi diagrams, check out Adam Dobrin's paper, "A Review of Properties and Variations of Voronoi Diagrams".

Creating a Voronoi Diagram

Let’s take a look at a simple example with two Voronoi sites, labeled A and B. Our goal is to divide the plane into two regions, where every point in a region is closer to its corresponding site.

This results in a basic Voronoi diagram. But what happens if we add more sites, let’s say, three? How do we divide the regions to ensure they meet the definition of a Voronoi diagram?

It all boils down to measuring the distance from every point in the plane to each site.

Distance Functions

To calculate the distance between points, we can use various distance functions. Some well-known options include:

• Euclidean Distance: The straight-line distance.
• Manhattan Distance: Distance measured along grid lines.
• Chebyshev Distance: The maximum of the horizontal and vertical distances.

Different distance functions produce different Voronoi diagrams, even with the same set of sites. Here’s an example comparing Euclidean, Manhattan, and Chebyshev diagrams:

Deciding where to put the points

Uniform Sampling

The simplest way to generate Voronoi sites is by random uniform sampling. However, randomness can result in clusters of points, making the diagram less visually appealing.

​Poisson Disk Sampling

To achieve more evenly spaced points, we can use Poisson Disk Sampling. This method ensures new points are placed near existing ones, but not within a certain “force field” radius.

While a bit fiddly to fine-tune, this approach results in a much more uniform distribution. Here’s a comparison of diagrams generated using uniform sampling versus Poisson Disk Sampling.

Colouring the diagram

Now that we have our Voronoi diagram, it’s time to add some colour. While you could assign random colours to each polygon, we wanted to make it special by using our company’s theme colours. However, we also wanted to avoid large sections sharing the same colour, keeping our socks visually varied and vibrant.

Here’s an example of what happens when neighboring sections share the same colour. This is what our diagram might look like with completely random colouring..

To ensure no two adjacent cells share the same colour, we turned to the Four-colour Theorem. This theorem states that any map, including our Voronoi diagram, can be coloured with no more than four colours so that no two neighboring regions share the same shade.

Knowing that a Voronoi diagram can be coloured with four colours is one thing. Actually doing it is another.

To colour our diagram, we used integer programming, a mathematical technique for solving constrained optimisation problems. The idea is to define a set of rules that determine a valid colouring, such as:

• If region A is blue, it can’t also be red.
• If region A isn’t red, green, or yellow, it must be blue.
• If regions A and B are neighbours, they can’t both be blue.

By carefully defining variables, we can convert these constraints into numerical equations. In Python syntax, you might encode the first two rules as:

Similarly, the neighbour rule is formulated as:

Once we’ve set up these constraints, the next step is finding values for a == red, a == blue, b == red, etc., that satisfy all conditions. This is where integer programming tools like PuLP (a Python library) help us find a valid solution.

Drawing The Borders

At this point, our Voronoi diagram is fully colored, but it’s missing one important detail, borders. Without clear thick borders, the diagram lacks definition. Here’s a comparison:

To draw the borders, we start by determining which tile each pixel in the image belongs to. Then, by shifting the image one pixel to the right and detecting where pixel values change, we identify the horizontal borders. Similarly, shifting the image one pixel up helps us find the vertical borders.

By combining these two methods, we outline where the borders should be. The final step is thickening the borders. We achieve this by convolving the border outlines with a solid circle, which evenly spreads the border outward. Taking a mask of all non-zero values in this convolved image results in crisp, thick borders.

Finally, this is what our diagram looks like with Poisson Disk sampling, thickened borders, and the Euclidean metric.

What’s Next?

With the pattern designed we sent them off to our favourite sock brand Defeet who do a custom service. They added our logo to the main section, the company name and Danny's initials (as the designer) to the sole of the foot. We ordered 120 pairs in various sizes.

We're absolutely delighted with the outcome, as are our customers and partners. There were so popular in fact that we've run out of size large so we're now looking at ordering another batch in different colours! We've got plenty of ideas for other mathematical designs though including the Delaunay triangulation, but we'll talk about that later in the year.