Einführung / Motivation In dieser Ausarbeitung meines Seminar-Vortrags wollen wir versuchen, folgendes Problem möglichst effizient zu lösen: Wir haben in einem zweidimensionalem Raum n Punkte gegeben. Jeder dieser Punkte hat eine Farbe, insgesamt kommen k Farben vor. Nun wollen wir verschiedene geometrische Objekte in unseren Raum legen. Diese Objekte sollen alle Farben überdecken, d.h. mindestens einen Punkt jeder Farbe beinhalten, und zugleich minimal bezüglich ihrer Fläche oder ihres Umfangs sein. Wir werden uns die meiste Zeit über mit minimalen achsenparallelen Rechtecken beschäftigen, für die wir einen Algorithmus mit einer Laufzeit von (  ) ( ) k k n n 2 log O herleiten werden. Anschließend werden wir noch zum Kleinsten Kreis kommen, den wir in der Zeit berechnen können, sowie zum (nicht unbedingt achsenparallelen) Schmalsten Streifen, den wir in der Zeit ( ) n kn O log () ( ) k k n log ²ƒ¿ O berechnen können. Des weiteren kann man allgemeine konvexe Polygone betrachten, was wir hier jedoch nicht tun wollen. Trotzdem sei erwähnt, das auch diese Probleme lösbar sind, bei einem minimalen Umfang in einer Zeit von    ( ) n k³ n nlog   + O und bei einer minimalen Fläche in einer Zeit von { } ( ) n k  , min 2 kn n n O log 2 2 + . Motiviert werden diese Probleme durch Lokalisierungs-Probleme. Nehmen wir beispielsweise an, jeder Farbe entspräche ein besti Also Farbe 1 = Schule, Farbe 2 = Supermarkt, Farbe 3 = Post, etc. Nun ist es klar, dass wir unseren Wohnort möglichst nahe an diesen Einrichtungen gelegen haben wollen. D.h. wir  wollen, dass von jedem Gebäudetyp ein Gebäude in unserer unmittelbaren Nachbarschaft liegt. Definieren wir nun diese Nachbarschaft noch als ein geometrisches zweidimensionales Objekt, z.B. einen Kreis, so gelangen wir automatisch zu einem der oben angesprochenen Problemen. Die folgenden Sätze und Algorith   en stammen größtenteils aus einem Paper „S   allest Color- Spanning Objects“ und sind nicht das Ergebnis eigener Forschung. Näheres zu diesem Paper sowie weiteren Möglichkeiten, an detailliertere Informationen zu den vorgestellten Algorithmen zu gelangen, sind unter den Literaturangaben zu finden. Smallest Color-Spanning Objects S. 2