Helly-Type Theorems for Approximate Covering

This paper considers the geometric covering problem. Given a collection F of convex sets in R^d and a convex set U, the geometric covering problem asks for a minimal subset of F such that the union of the elements in this subset cover U. The problem is NP-hard in general. This has led to a wide range of approximation algorithms being developed, usually relaxing the condition of minimality. In this paper the authors pursue a different direction by allowing a small volume ε of U that remains uncovered, calling it an ε-covering. Interestingly, it turns out that under certain assumptions the size of the minimal ε-covering is independent of the size of F, which implies that arbitrarily large ε-coverings do not exist. This is in contrast to the exact covering case.

Contact: Yves Brise, ybrise@inf.ethz.ch, CAB G36.2, Tel. 044-632 7796.

Euclidean Shortest Paths in the Plane

The problem is easily stated as follows. Given two points s and t, and a number of polygonal obstacles in the plane, find the shortest path between s and t, avoiding all obstacles. In this paper the authors present an optimal O(n log n) algorithm. Note that the 3 dimensional counterpart is NP-hard for any L^p metric. The paper is pretty long, and the algorithm employs some geometric constructions that become very technical if explained in full detail. One of the major challenges of a talk about this paper will be to select suitable material. Note that there is an earlier version of the algorithm that runs in O(n log² n) and that was published by the same authors in the Proc. of the 34^th FOCS, 1993, in the form of an extended abstract. This condensed description of essentially the same algorithm might be a good entry point for somebody interested.

Contact: Yves Brise, ybrise@inf.ethz.ch, CAB G36.2, Tel. 044-632 7796.

Consensus-halving via theorems of Borsuk-Ulam and Tucker

The study of fair division problems is concerned with finding ways to divide an object among several parties according to some notion of fairness. This paper discusses consensus-halving: the division of an object into two portions so that each of n people believes the portions are equal. The authors use the combinatorial version of a famous topological theorem to provide a rather simple proof which gives an algorithm to find an approximate solution.

Contact: Anna Gundert, anna.gundert@inf.ethz.ch, CAB G19.2, Tel. 044-633 3222.

Algebraic topology and concurrency.

In this article, concepts from homotopy theory, in algebraic topology, are used to study concurrent programs. Information about important properties of the program, such as deadlocks, unreachables, serializability, essential schedules, etc. can be described by modelling the space of possible executions as a topological space with a time direction, which is then studied up to .elastic deformation. or homotopy. In fact, it is not quite ordinary homotopy that has to be used, but rather a .directed homotopy. that does not reverse the flow of time. This application was one inspiration for the development of a new field, "directed topology", in algebraic topology.

Contact: Anna Gundert, anna.gundert@inf.ethz.ch, CAB G19.2, Tel. 044-633 3222.

Minimum Weight Triangulation

A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard. We use a reduction from PLANAR-1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using geometric inclusion and exclusion criteria for MWT edges, such as the diamond test and the LMT-Skeleton heuristic, as well as dynamic programming on polygonal faces.

Contact: Michael Hoffmann, hoffmann@inf.ethz.ch, CAB G33.1, Tel. 044-632 7390.