FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik

Vortrag des Informatik-Kolloquiums

Wir betrachten zwei geometrische Distanzprobleme, die bei der Bewertung und Planung von Standorten auftreten. Beim ersten Problem soll die Güte eines Transportwegs C gemessen werden, indem sein maximaler Umweg bestimmt wird. Dieser ist definiert als das Maximum aller Quotienten aus der Kurvenlänge 
von C zwischen zwei beliebigen Punkten p,q in C und der Länge einer kürzestmöglichen Verbindung von p nach q. Wir geben Algorithmen mit Laufzeit O(n polylog n) für die Berechung des maximalen Umwegs einer Kette aus n Kanten in verschiedenen Umgebungen an.
Beim zweiten Problem soll ein Standort für ein neues Geschäft so bestimmt werden, dass seine Voronoi-Region im Diagramm der Konkurrenzgeschäfte eine möglichst große Fläche bekommt. Wir zeigen, dass diese Flächenfunktion höchstens ein lokales Maximum aufweist, wenn die Menge der Voronoi-Nachbarn vorgegeben ist und diese in konvexer Lage sind.