Scot Drysdale -Dartmouth College

The Rectilinear Minimum Link-Distance Problem in Three Dimensions

Abstract: In this talk we consider the Rectilinear Minimum Link-Distance Problem (also known as the Minimum Bends Path Problem) among rectilinear obstacles in three dimensions. The problem is to find the shortest path between two points in space that avoids passing through obstacles, where the path consists of a sequence of segments parallel to the coordinate axes. The faces of the obstacles are perpendicular to a coordinate axis. The distance is measured in the number of segments (links) required rather than Euclidean length.

The problem is well studied in two dimensions, where it arises in VLSI layout and wire-routing problems. It is less studied in higher dimensions. We give an algorithm which solves the three dimensional problem in worst-case O(β n log n) time, where n is the number of corners among all obstacles, and β is the size of a BSP decomposition of the space containing the obstacles. It has been shown that in the worst case β = Θ(n^3/2), giving us an overall worst case time of O(n^5/2 log n). However in many practical circumstances we will have β ≈ O(n). The best previously known algorithm, from a robotics paper, has a worst-case running time of O(n³).

As part of the talk I will describe a version of a 2-D segment tree that allows insertion and deletion of rectangles and keeps track of the part of the plane currently covered. It allows queries of the form "Is any part of this rectangle currently covered?" and allows projection of all of the rectangles onto the x or y axis.

Colloquium - 16:00

Dirk Schlatter -Humboldt-Universität zu Berlin

Restricted random graph processes

Abstract: Let C be a set of graphs which is closed under isomorphism and subgraphs, and consider the following variant of the classic random graph process G(n,m): Start with an empty graph on n vertices, choose the next edge uniformly at random from all unconsidered ones, but accept it only if the resulting graph remains within C. Such a process is said to be "rich", if the probability that it finally contains any given graph in C is asymptotically 1. We will discuss sufficient conditions for richness.