Are you fresh off the back of the long weekend and looking to sink your teeth into some combinatorics and induction? Great then you’ve come to the right place so pull your discrete mathematician stocking over your head and let’s get started. Welcome to Gem Island! Home to N happy islanders. Each of which has exactly one gem. Each night something peculiar happens. One of the gems on the island is…
Imagine a polygon, like the blue one below. Where should you stand in that polygon such you are as far as possible from your nearest vertex? This seems like a useful thing to be able to calculate in 2020 (hope this blog post ages well). Ostensibly this should be easy to compute too, but it’s not obviously that the red dot in the image below is in fact the furthest point from any of the polygon…
Have you ever wondered what the probability is of making it through a sequence of traffic lights without stopping? Me neither. But some people do so let’s try and solve that problem. It’s something that appears in everyday life for example my walk from home to DroneDeploy taken me through 16 traffic lights. Let’s say we begin at position X=0 at time T in seconds and start walking as 1 meter per…
I was watching the Fleet Week display by the Blue Angels yesterday and we were talking about if you could determine where an aircraft was based on the sounds you were hearing from the engine. Say we have an aircraft at some unknown position flying at a constant linear velocity. If the engine is emitting sound at a constant frequency and as soon as we start hearing the engine we start recording the…
We have two convex polygons P and Q each moving at constant velocities Vp and Vq . At some point in time they may pass through one another. We would like to find the point in time at which the area of their intersection is at a maximum. Here is a simple visualization, where the yellow area represents the intersection and the arrow heads represents the velocity of the polygons. Let’s first look at…
Imagine you are looking to intercept a communication that can happen between two people over a telephone network. Let’s say that the two people in question are part of a larger group, who all communicate with each other (sometimes via other people in the network if they don’t have their phone number). We can represent this as a graph where the vertices are people and edges connect two people if…
If you have N points in the plane what is the largest subset of those points such that each point is within a distance of D of all the others. It seems pretty innocuous right? Turns out it’s a great big beautiful disaster. Here’s a example of N = 10 points where the maximum subset are the points collected with dotted lines which are each within a distance D of each other. There is no bigger set.…
Some applications of photogrammetry require us to collect a number of overlapping aerial images covering an area. The more overlap the better, as more overlap in pairs of images gives us a higher result in some applications. However in other applications we are actually looking for as few images as possible from the set that still cover the area of interest without any gaps. Framed another way -…
This post is based on a question from the Challenge 24 competition in 2016 where we were given a photograph of each of the denominations of Hungarian currency, called Forints . In addition given a number of photos of piles of coins (some of them counterfeit) and we had to compute the total value of money automatically. First let’s look at the template and see how we can easily extract the location…
This post is based on a question asked during the Challenge 24 programming competition. Given the locations of a number of land mines as X and Y coordinates and their blast radius R . What is the minimum number of mines that need to be detonated such that all mines are detonated. When a mine is detonated it detonates all mines within its blast radius and the process repeats. Here’s a simple…