Checkpoints along a Highway

140 Views Asked by At

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.

2

There are 2 best solutions below

6
On

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.

1
On

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