In a few places I mentioned that besides the "standard" approaches to G (including the actual solution at the WF), there's a more geometric approach. Let me describe it here.

First, a recap of the problem. We're given a rectangular area with a triangulation, with up to 50K vertices. Each of the triangulation vertices has a distinct height, and the height within triangles is linearly interpolated. We're asked to find the length of the shortest path from the east edge of the rectangle to the west that all lies on one height. Additionally, there are no triangulation vertices (except corners) on the east and west edges.

First (this is common to both solutions), let's look at the set of points at a given height H. The intersection of this set with any triangle is either empty, a single vertex (the unique vertex of height H), or an interval. So, the set of points at height H forms a set of paths (which interesect triangulation triangles at intervals), and these paths can terminate by:

• being a cycle (which is not interesting, as a cycle can't touch both the west and east edge of the rectangle)
• one or both ends of such a path can be in the unique vertex of height H
• one or both ends of such a path can reach one of the four edges of the rectangle.

Also, note that if we shift H a bit (without crossing the height of any triangulation vertex), then the length of the intersection of the path with any triangulation triangle is a linear function of H, and so the length of a whole path is a linear function of H. This implies, in particular, that the function "height to length of shortest path" is piecewise linear; and that the minimum length of a path is attained by a path that goes through a triangulation vertex.

The non-geometric solution at this point sweeps by height, and uses some data structure to keep track of the chains of paths and their lengths. I'll not describe this. Instead, I'll describe a more geometric solution.

First, let's do a quadratic solution (which is too slow). We can just run a tree search from the east edge at each candidate height, trying to reach the west edge. Each such tree search visits every triangle at most once, so it's linear (assuming we first precalculate for each triangle the triangles adjacent to it), so the whole thing is quadratic. Now, we'll improve on this.

We will try to run the tree search in "batch mode", processing multiple heights in one step. So, we'll maintain a piecewise linear function (by holding two range trees, one for the linear coefficient, and one for the constant) mapping height to length of path thus far. We begin at the east edge, and the function is constant zero. Now, there's a single triangulation triangle touching the east edge, call it ABC, with A and B being on the east edge. To avoid analysing the corners of the rectangle, we can run a tree search from A and from B to begin with.

Assume first h(C) > h(B) > h(A) (where h(P) denotes the height of point P). Then all the paths from the east edge (with the possible exception of the path through B, which we already handled) go through this triangle and hit edge AC (because the whole edge BC is higher than anything in the interior of AB). So, we can add the appropriate linear function to our range tree, and now go to process the edge AC, or rather, the unique triangle on the other side of AC. The case where h(C) is the smallest is symmetrical.

The other case is when, say, h(B) > h(C) > h(A). Then some of the paths go to the edge BC, some go to CA, and there's the path that goes at height h(C) which hits vertex C, and might do all sorts of things from there (because there might be a large number of paths at height C leaving that vertex). So, our tree search branches — it has to search the triangle on the other side of BC, the triangle on the other side of CA, and then also follow all the paths going out from C.

So, what's the time complexity on this? It's actually almost OK. If only these three branches (through BC, through CA, and through C) didn't visit the same triangles, we'd be fine — because then the whole tree search would visit each triangle at most once, and so the complexity would be O(N log N), with the log for maintaining the range trees. Alas, the world is not that great. Can the search through BC and the search through CA visit the same triangle? Yes, they can. The easy example is if there is only one path at height h(C) leaving C (and going to the west edge), through some triangle CDE. Then both the tree search through BC and the tree search through CA will visit triangle CDE, for height C+eps and C-eps, respectively. And if that happens repeatedly (and it can, we have testcases like this), this will make the whole thing quadratic.

We need to deal with this. In the specific case that we described, the way to deal with this is simply to follow one branch of the tree search (say, the one through BC), until it hits triangle CDE. Then pause that branch (having updated the height-to-path-length function for the heights in range, say, (h(C), h(D))), and switch to the branch through CA. Once that branch also hits CDE, having updated the function for, say, (h(E), h(C)), we can simply continue out of CDE through edge DE, for the whole range of heights (h(E), h(D)) — note that for height h(C) we don't need to update the function at all, whatever the cost of getting to C was at triangle ABC is accurate.

The more general case can be more complex — there could be multiple paths leading out of C, but some of them might cycle back to C again. A key observation is that if there are at least two paths out of C that hit some boundary of the rectangle (not counting the one through which we came in), then these two paths are triangle-disjoint (that is, they don't pass through the same triangles); and they also fully separate the AB-branch of the tree search, from the BC-branch. So, the only case we need to handle is the case where there is exactly one path out of C hitting the boundary, plus possibly some cycles.

The problem is that we need to detect this without actually traversing this path that goes to the boundary (because that path might be of length O(N), and we might need to do this detection O(N) times). Notice that, not counting the path we came in through, there's an odd number of paths going out of C, because the paths alternate between "higher on the left, lower on the right" and "higher on the right, lower on the left". So, what we actually do is we order these outgoing paths in a clockwise order, and traverse the second one (or any even-indexed one). It either cycles (in which case we remove both the exits from C that compose the cycle, we can also remove anything in the middle, as that has to be smaller cycles enclosed in the cycle we just found), or it hits the boundary. If it hits the boundary, then there has to be a path to the left of it that hits the boundary (because there's an odd number of paths to the left, so they can't all pair up in cycles), and a path to the right that hits the boundary. That means that:

• the tree searches through BC and CA are triangle-disjoint
• and they're also all triangle-disjoint from the path that we just traversed

So, to recap — we will advance the tree search triangle by triangle. We'll have some triangles marked as "stoppers" (this is the triangle CDE, above), which have to be reached twice in order for the search to proceed. If we enter a triangle, then:

• if it's a stopper, and it hasn't been reached yet, we remove the "stopper" mark from it, and terminate this branch.
• if we entered through an edge AB, and the height of the third point C is the largest, say h(C) > h(B) > h(A), then we increment the height-to-length function appropriately, and proceed to the triangle on the other side of AC. The other cases where h(C) is smallest or largest are similar.
• if we entered through AB, and h(B) > h(C) > h(A), then we proceed clockwise through all other triangles incident to C. We check which ones have paths of height C outgoing, take any even-indexed path, and follow it.
• If it ends up going back to C, we remove both the triangles through which the cycle touched C, and try again with an even-indexed path.
• If it hits the boundary, we remember this fact, and continue processing even-indexed paths.
• If we're left with only one path, and we haven't hit the boundary yet, then we mark the triangle CDE through which this path exits as a "stopper", and then branch into tree-searching BC and CA.
• If we found at least one even-indexed path leading to the boundary, we now also check all the odd-indexed paths except the first and last one (because the first and last one will be checked by tree-searches through BC and CA). If any of them hit the west boundary, we take the current value of the function at C plus the length of the shortest path from C to the boundary as a candidate solution; and then proceed to branch into BC and CA.