umma.dev

Martin Goetz, whilst working at one IBM's competitor Applied Data Research (ADR) patented the sorting system. His patent a program that could sort data stored across magnetic tape drives using an efficient merge-sort approach. The USPTO rejected it twice on the grounds that it described a "mental process." Goetz appealed, and in 1968 the patent was granted.

The technical substance is a merge-sort variant optimised for tape I/O constraints in the 1960s. Sequential tape reads are cheap; random seeks are expensive. The algorithm minimised backward seeks by structuring passes to move data in one direction as much as possible - a hardware-aware design decision baked into the algorithm itself.

Once the USPTO granted it, the floodgates opened. Within a decade, software patents became routine. ADR themselves ended up suing IBM for antitrust violations related to IBM's bundling practices - a separate legal saga - but the Goetz patent was the first domino.

Xerox PARC in the 1970s was producing ideas at a rate that the rest of the industry would spend the next thirty years commercialising. The Alto computer had a bitmap display, a mouse, overlapping windows and icons. The team filed US4115854A in 1975 to cover the method by which a computer generates a structured, interactive display - moving beyond terminals printing text in sequence.

The patent's claim is about the relationship between an in-memory model and a visual representation. Rather than treating the screen as an output device that receives characters, the method describes maintaining a structured data model of display objects and rendering that model to the bitmap. Update the model, the display updates. This is the conceptual foundation of every UI framework written since - the separation of state from rendering.

What Xerox did not do is commercialise it effectively. Apple's engineers visited PARC in 1979 and saw the Alto running. Steve Jobs famously walked out convinced he had seen the future. The Mac shipped in 1984. Microsoft Windows followed. Both built on ideas that Xerox had patented but never turned into mass-market products. Xerox later sued Apple and Apple countersued Microsoft. The litigation ran for years and largely resolved on procedural grounds, leaving the underlying technical IP questions unanswered.

The engineering lesson that having the invention and holding the patent does not automatically translate to owning the market. The gap between "we filed this" and "we shipped this" is where most of PARC's value evaporated.

Standard Dijkstra's algorithm finds the shortest path from a source node to all reachable nodes in a weighted graph. For GPS routing on a road network, you do not need all reachable nodes, you need one destination.

Imagine routing from London to Edinburgh. Standard Dijkstra starts at London and expands outward in every direction. A growing frontier shaped roughly like a circle. By the time it reaches Edinburgh, it has also explored enormous swaths of Wales, the Midlands, and northern England that are completely irrelevant to the answer. The search area scales with the square of the distance.

Bidirectional Dijkstra runs two simultaneous searches. One forward from the source, one backward from the destination. Each frontier expands as a circle with half the radius. Two half-radius circles together cover roughly half the area of one full-radius circle. The search terminates when the two frontiers meet. Honda's patent applies this bidirectional approach specifically to the problem of planning multiple alternative paths (not just the single shortest route) but a set of plausible routes a driver might want to choose between.

The implementation challenge is the termination condition. With standard Dijkstra, termination is clean, you have settled the destination node. With two simultaneous frontiers, determining when they have definitively met and that no shorter path exists through unexplored territory requires careful bookkeeping. The patent describes a method for doing this correctly while simultaneously tracking multiple candidate path combinations. This is significantly more complex than the textbook bidirectional Dijkstra description.

Honda was building this for in-car navigation systems at a time when handheld GPS was still early. The patent is a window into how seriously the automotive industry was thinking about routing algorithms two decades before most engineers would have expected them to.