The Longest Sailable Line on Earth: What Branch-and-Bound Taught Me About Pruning AI Search Spaces

A couple of years ago I was building the candidate-generation step for a maritime routing feature — the part of the pipeline that proposes plausible long-haul shipping lanes before an ML model scores each one for fuel burn, weather exposure, and piracy risk. It worked fine in a demo with a handful of ports. The moment we pointed it at a real port catalog, the number of candidate great-circle routes exploded into the tens of thousands, and our GPU inference bill exploded right along with it.

While I was staring at that bill, a teammate dropped a link in Slack to an old arXiv paper with a delightfully unserious title: Longest Straight Line Paths on Water or Land on the Earth, by Rohan Chabukswar and Kushal Mukherjee. I expected a fun math curiosity. What I actually got was a working example of exactly the mistake I'd just made — throwing an expensive search at a problem that a cheap geometric bound could have solved first.

This post is my walkthrough of what that 2018 paper actually did, grounded in what it says rather than in the "cool map" version of the story that went around Reddit and tech blogs at the time. Then I'll show the version of the same trick I ended up rewriting my routing pipeline around, and where it does and doesn't apply if you're building something similar for an AI product.

The Reddit map that nobody could verify

The paper's own introduction traces the problem back to December 29, 2012, when a Reddit user going by kepleronlyknows (real name Patrick Anderson) posted a map to r/MapPorn claiming to show the longest straight line you could sail on Earth without hitting land — a route starting near Pakistan, threading past the southern tips of Africa and South America, and ending somewhere out in the far eastern Pacific near Russia. It's a striking image: on a flat map the "straight" line looks like a wandering curve, because on a globe, straight lines are great-circle arcs.

Anderson never published the method or the code behind the map, just the picture. For years it circulated as internet lore — plausible, widely reposted, and completely unverified. That's the gap Chabukswar (at the time with United Technologies Research Center Ireland) and Mukherjee (IBM Research India) set out to close: not just "is this particular map right," but a general method for computing the longest sailable straight line, and its mirror-image problem, the longest straight line you could drive without crossing a major body of water.

What I like about this framing is that it's explicit about being an optimization problem, not a trivia question. The paper describes it as chaotic because of islands, lakes, and the fractal nature of coastlines — meaning small changes in a candidate line's heading can flip it from "clear" to "hits land" unpredictably, which rules out any solution that assumes the search space is smooth or well-behaved.

Why you can't just brute-force a sphere

Every straight-line path across the surface of a sphere is a segment of a great circle. So finding the longest sailable line means finding two points on Earth's oceans such that the entire great-circle arc between them stays over water — and finding the longest driveable line means the reverse, an arc that never crosses a major body of water. Checking a single candidate arc is easy: you sample points along it and check the terrain. Checking all candidate arcs is where things fall apart.

The elevation and bathymetry data the paper uses is ETOPO1, a 1 arc-minute global relief model that combines land topography and ocean depth into roughly 233 million grid points, at about 1.85 kilometers of resolution near the equator. There's a detail here I hadn't expected: ETOPO1 ships in two versions, "Ice Surface" and "Bedrock," and the paper deliberately picks Ice Surface for both problems — a ship can't sail across an ice sheet, but a vehicle technically can drive over one, so the same dataset choice quietly encodes both physical constraints at once.

Even with that data in hand, the naive approach — check every pair of ocean grid points, or every pair of coastline points, as a candidate line — is a non-starter. The paper is upfront that the authors tried a brute-force search first and abandoned it; with hundreds of millions of points, an exhaustive pairwise check isn't a matter of a slower run, it's a search space too large to finish on any reasonable timeline. That's the actual reason the rest of the paper exists: they needed a way to rule out huge swaths of candidate lines without individually testing each one.

How branch-and-bound actually prunes the tree

Branch-and-bound is an old technique from combinatorial optimization, and it's worth being precise about what the two halves of the name mean, because "bounding" is doing almost all of the work here. Branching is the part that looks like brute force: you organize the space of candidate solutions into a tree, where each node represents a subset of possibilities. Bounding is the part that isn't brute force at all: for each node, you compute a cheap upper bound on the best possible solution that could still be hiding inside it, and if that bound is worse than the best solution you've already found, you throw the entire branch away without looking inside it further.

What makes this paper's version work is finding a bound that's both cheap to compute and mathematically valid for great-circle geometry — a property of the arc that lets you say "no path starting in this region can possibly beat our current best" without having to trace every arc all the way to a coastline. Roughly, the process looks like this:

• Start with the full space of candidate start and end regions on the globe.
• For a given branch (a region of candidate start/end points), compute a great-circle-based upper bound on the longest path reachable from it.
• Compare that bound against the length of the best full solution found so far.
• If the bound can't beat the current best, discard the entire branch — no further checking needed.
• If it might beat the current best, subdivide the branch into smaller regions and repeat the process on each one.

The tree keeps shrinking because most branches get eliminated early, before the algorithm ever has to trace an arc point-by-point across the ETOPO1 grid. That's the entire reason this problem went from "computationally hopeless" to "runs on a laptop" — not a faster computer, a smarter way to avoid doing most of the work in the first place.

Applying the same instinct to my AI candidate-generation pipeline

My routing problem wasn't identical, but the shape of the mistake was. I was generating every candidate great-circle corridor between port pairs and handing each one straight to an ML risk-scoring model before checking whether the corridor was even geographically sane. A lot of those candidates crossed continents. The model didn't know that — it just scored whatever it was handed, which meant we were paying full inference cost for garbage.

Here's roughly what the naive version looked like:

def generate_scored_corridors(ports):
    candidates = []
    for origin in ports:
        for destination in ports:
            if origin == destination:
                continue
            arc = great_circle_arc(origin, destination)
            score = risk_model.predict(arc)  # expensive GPU call, every time
            candidates.append((origin, destination, score))
    return candidates

For a batch of a few hundred ports that's tens of thousands of model calls, and a meaningful fraction of them are routes that cross Panama, cut through the Sahara, or clip an island chain — dead on arrival, geographically. We were letting the expensive part of the system do the cheap part's job. The fix was to add a bounding pass before the model ever gets invoked, using the same idea from the paper: a cheap check against a coarse bathymetry raster that can rule a corridor out (or flag it as needing subdivision) without ever calling the scorer:

def generate_scored_corridors(ports, land_raster, max_land_fraction=0.0):
    candidates = []
    for origin in ports:
        for destination in ports:
            if origin == destination:
                continue
            arc = great_circle_arc(origin, destination)
            if land_fraction(arc, land_raster) > max_land_fraction:
                continue  # pruned before the model ever sees it
            score = risk_model.predict(arc)
            candidates.append((origin, destination, score))
    return candidates

The land_fraction check is orders of magnitude cheaper than a model call — it's a raster lookup along a sampled arc, not a forward pass. In our case it cut the number of model invocations by roughly 95% for the same port catalog, and the corridors that did reach the model were ones actually worth scoring. None of this made the model itself faster or smarter. It just stopped wasting it on inputs that geometry alone could have rejected.

The numbers the paper actually landed on

It turned out kepleronlyknows had it right. The paper's branch-and-bound search over the water problem confirmed the same route from the original Reddit map: a straight line beginning near Pakistan, running through the Arabian Sea and past the southern tips of Africa and South America, and ending in the far eastern reaches of Russia, for a total length of about 32,089.7 kilometers (19,939 miles). The authors report finding it in around 10 minutes of computation on a standard laptop.

The converse problem — longest straight line drivable without crossing a major body of water — took longer to search and produced a very different-looking route: from near Quanzhou in eastern China, across 15 countries, ending in Sagres on Portugal's Atlantic coast, a path of about 11,241 kilometers.

The land path is a third of the distance but took roughly four and a half times longer to compute, which is a nice sanity check on how branch-and-bound behaves in practice. Length alone doesn't predict search cost — branching cost tracks how often a candidate path comes close to a border it might cross, and a route threading 15 countries generates far more of those close calls than one crossing open ocean where the only obstacles are occasional islands.

What I'd check before trusting a result like this again

Once I'd applied this to my own pipeline, I got a lot more skeptical of what "verified" actually means when the verification runs on a fixed grid. ETOPO1 is a real, carefully built dataset, but it's a static 2009 snapshot at roughly 1.85 km resolution — it's not resurveyed continuously, and it can't represent anything narrower than its own grid spacing.

That's not a knock on the paper — the authors are explicit about which dataset and which version of it they used, which is exactly what let me go check this in the first place. It's a reminder for anyone building something similar on top of a discretized geometric proxy: whatever grid or raster you're pruning against becomes part of your answer's definition, not just an implementation detail you can ignore once the number comes out. The same caveat applies directly to my routing pipeline — a corridor that clears our land-fraction check on a coarse raster isn't automatically safe at the resolution a real ship needs.

None of this changes the core lesson I took from the paper, though. If you're building the candidate-generation step in front of any AI model — routing, matching, ranking, whatever — it's worth spending an afternoon asking whether there's a cheap, provably valid bound that rules out most of your candidates before the model ever sees them. Not every search problem has one; if your candidate space doesn't have some property you can check cheaply and soundly, branch-and-bound won't save you and you're back to sampling and heuristics like everyone else. But when that bound does exist, it's usually worth more than the next round of model tuning, and it's a lot cheaper to build.

Sources: Chabukswar, R. & Mukherjee, K. — Longest Straight Line Paths on Water or Land on the Earth (arXiv:1804.07389)