Minimum cell connection and separation in line segment arrangements

Let S be a set of segments in the plane and let x, y be two points in the plane. We shall discuss the following two optimization problems:

(i) find the smallest subset S’ of S such that any path from x to y crosses some segment of S’.
(ii) find the smallest subset S’ of S such that there is path connecting x to y disjoint from SS’.

Joint work with Helmut Alt, Pannos Giannopulos, and Christian Knauer.