| [home] - [up] |
Abstract: I will describe an efficient algorithm to compute the shortest path homotopic to a given path on a given combinatorial surface. The algorithm has two phases. In the preprocessing phase, we construct a set of simple cycles, each as short as possible in its homotopy class, that decompose the surface into topological disks, each with the same number of edges. This decomposition allows us to approximate the given irregular metric with a standard hyperbolic metric, defined by a regular tiling of the hyperbolic plane by right-angled k-gons, for some even k>4. In the query phase, we exploit this hyperbolic structure and techniques in combinatorial group theory to reduce the shortest-path search to a small subset of the universal cover. Dijkstra's algorithm then finds the true shortest path quickly.
This is joint work in progress with Eric Colin de Verdiere.
Colloquium - 16:00
Abstract: A partial order P is called a semi-order if there exists a function I which assigns to each element x of the order a closed unit interval I(x) = [ix, ix+1] of the real line so that x < y in P if and only if I(x) < I(y) (i.e. if ix+1 < iy). The online chain partitioning of a semi-order can be viewed as a two-person game. The game is played in rounds. The first player builds the online order, one point at a time. The second player responds by making an irrevocable assignment of the new point to one of the chains of the chain partition. In the upgrowing variant of the game the new point presented by the first player has to be a maximum element in the present order. The performance of the second player is measured by comparing the number of chains used with the the number of chains used by an optimal offline algorithm, i.e., with the width of the order. We prove a lower bound of 8w/5 and an upper bound of 5w/3 on upgrowing semi-orders of width w.