# Checkpoints along a Highway

This is a new puzzle I'm creating. Advices welcome.

Preliminaries:

Imagine a car highway. This highway can be described as the smooth connection of smaller segments consisting of straight lines, and arcs of (for simplicity) circles bending left or right.

Mathematically, each of these segments can be characterised by two variables: the length of the arc $d$, and an associated angle of the arc $a$. This angle can be understood as the angle that corresponds to the beginning point of the arc if the arc were to be enclosed in a right triangle such that one of its sides is tangent to the arc at that beginning point.

(If the above is not clear, read the following: Consider a straight line $AB$ of length $d$, with beginning point at $A$ and ending point at $B$. Now, take point $B$ and bend this line uniformly to one of its sides in order to form an arc (part of a circle). Denote this new end point as $C$. Then, the angle that $CAB$ form is $a$. For example, if $a=45°$, then this arc is a quarter of a circle; if $a=90°$, this arc is half of a circle; if $a=0°$, this is just a straight line.)

In order to make sense of left and right, assume that the sign of the angle tells whether the highway turns left (+) or right (-).

Now, define a Segment $S_{j}$ as the pair $\{d_{j},a_{j}\}$. Then, a Highway ($H$) can be defined as a connected sequence of Segments, always connecting the end of a segment with the beginning of a new segment. This is, $H_{n}= \{S_{1},S_{2},S_{3},...,S_{n}\}$. Note that the connection is smooth. This is, the direction at the end of $S_{j}$ is the same than the direction at the beginning of $S_{j+1}$.

So, for example, if $S_{1}=\{1,0°\}$, $S_{2}=\{2,45°\}$, $S_{3}=\{1,-45°\}$, and $S_{4}=\{2,0°\}$, then $H_{4}=\{S_{1},S_{2},S_{3},S_{4}\}$ is a highway which starts in a straight line for a distance of 1 (say, km), then bends left 45 degrees for 2 km, then bends right for 1 km, and finally goes straight for 2 km. Thus, the first and the last segments of the highway are parallel.

Setup:

Consider an arbitrary highway $H_{n}$. The highway has two lanes, each of size $L$ (its perpendicular sections can be represented like this, |----|----|, where each segment is of size $L$). The construction of the highway is done from the middle point of it. This is, build $H_{n}$ and then attach to its two sides a parallel copy of it at a distance $L$.

Imagine two identical cars, one on each lane, standing at the beginning of the Highway, side by side. Imagine now that they start moving at equal speed, keeping their respective lanes at all times.

Question:

Describe a method (with formulas) to characterise all those points along the highway where the cars are side by side, as in the starting line.

(So, if this would be a race, you want to describe a mathematical method to find where you could place checkpoints in order to compare cars average speed using the recorded times and equal distances, for any given highway structure)

Note: For simplicity, angles range between -90° and +90°. Similarly, assume that $d$ is positive.

• I think you should clarify the bending of the line is the first paragraph. Without the second paragraph it was ambiguous as to how the line was bent. More specifically, you probably should specify that the beginning of the line $A$ is anchored at the origin and the end $B$ is bent with a uniform curvature in the counterclockwise direction to $B'$ to form the angle $a = \measuredangle{BAB'}$. Sep 2, 2015 at 8:42
• wouldn't 45 degrees lead to an eighth of a circle? I believe that 90 degrees is a quarter of a circle
– Ivo
Sep 2, 2015 at 12:04
• Thanks, I will clarify. @IvoBeckers, the angle is defined between the linear projection of the actual direction where the segment begins and the line that connects this beginning point with the ending point. Sep 2, 2015 at 16:39

Take the cumulative sum of the angles. You can place a checkpoint wherever the sum is zero.

This answer assumes that the radius of every bend is at least $\frac{L}{2}$. The way that the bend is defined in the questions, a bend of $a$ degrees produces a circular arc spanning $2a$ degrees. Over this bend, the difference between the lanes' lengths is $\frac{aL\pi}{90}$, no matter what the length of the bend is. This means that we can simply sum the angles to determine how much farther one car has traveled than the other.

• Let's say you have a segment left of 45 degrees followed by a segment right of 90 degrees. Am I right in saying that there could be a checkpoint exactly halfway of the second segment?
– Ivo
Sep 2, 2015 at 12:09
• I think a conclusion would then be: Checkpoints are at all points of the road where the road's direction is exactly parralel with the road's direction of the starting point
– Ivo
Sep 2, 2015 at 12:15
• @IvoBeckers Yes for the first comment. Not quite for the second, because the road could possibly be turned by 360 degrees or more at some points.
– f''
Sep 2, 2015 at 12:58
• ah yes, you're right
– Ivo
Sep 2, 2015 at 12:59
• The sum of the angles is not enough because you can have the same angle with different distances to cover. The larger the distance, the smaller the change in the curvature (the derivative, if you prefer). Sep 2, 2015 at 16:34

I made a small program in Lua which should give the right answer. This is the code:

H = {{3,0},{1,45},{3,-90},{4,45},{1,0}};
cumulativeDistance = 0;
cumulativeAngle = 0;
for index, S in ipairs(H) do
local distance = S[1];
local angle = S[2];
local newCumulativeAngle = cumulativeAngle + angle;
if math.abs(newCumulativeAngle) <= math.abs(angle) and angle ~= 0 then
print("There is a checkpoint at distance " .. (cumulativeDistance + (math.abs(cumulativeAngle)/(math.abs(cumulativeAngle)+math.abs(newCumulativeAngle)) * distance)));
end
if (cumulativeAngle == 0 and angle == 0) then
print("Between distance " .. cumulativeDistance .. " and distance " .. (cumulativeDistance + distance) .. " is a road where you can make a checkpoint everywhere");
end
cumulativeAngle = newCumulativeAngle;
cumulativeDistance = cumulativeDistance + distance;
end


You can copy and paste it on http://www.lua.org/cgi-bin/demo to check it out. Change H however you want. My example gives the following output:

Between distance 0 and distance 3 is a road where you can make a checkpoint everywhere
There is a checkpoint at distance 3.0
There is a checkpoint at distance 5.5
There is a checkpoint at distance 11.0
Between distance 11 and distance 12 is a road where you can make a checkpoint everywhere

• I will look at the code once I have time. In any case, I'm interested in the mathematical solution and its intuition (the target audience are not required to know programming languages). Can you expand on these two for your particular solution? Sep 2, 2015 at 17:23