Historische Entwicklung

In der Geschichte trat das Problem zum ersten Mal in relevanter Weise bei einem Herrn namens Ulf Grenader auf, der das Problem in 2-dimensionaler Form vorliegen hatte, es aber versuchte auf eine Dimension zu reduzieren. Dieser Herr schrieb Algorithmus A1. Schnell aber war klar, daß er zu langsam war und viel zu viel Zeit zur Berechnung der Teilprobleme benötigte. Nachdem er sich einige Zeit mit dem Thema auseinandergesetzt hatte schuf er dann Algorithmus A2.
Da aber auch A2 weiterhin ziemlich viel Zeit für das Problem benötigte, bat er 1977 Michael Shamos um Hilfe, der ihm "über Nacht" Algorithmus A4 kreierte. Danach waren beide der Überzeugung, daß dies die optimale Lösung des Problems sei, da bereits viele ähnliche Probleme der Zeit in O ( n log( n ) ) gelöst worden waren und für diese die nicht-Existenz eines schnelleren Algorithmus bewiesen war.
Als einige Tage später Shamos beim Carnegie Mellon Seminar sein Problem an Jay Kadane herantrug, schaffte dieser es innerhalb weniger Minuten, die These mit O( n log( n ) ) zu widerlegen, indem er Algorithmus A5 niederschrieb. Da für alle sub-linearen Algorithmen gezeigt werden kann, daß sie das Problem nicht korrekt lösen können, ist somit eine sehr effiziente Lösung für das Problem gefunden.
Jetzt, wo Ulf Grenader sein Problem gelöst hatte, konnte er sich wieder dem 2-dimensionalen Problem widmen. Allerdings ist auch 2 Jahrzehnte später ( da erschien das Buch ) das Problem weiterhin ungelöst ...