EADS Mini-Workshop on Computational Geometry

This EADS mini-workshop will consist of four talks.

A Generic Method for Finding Coresets for Clustering Problems

Mehran Mehr (Eindhoven University of Technology)

Joint work with: Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Ali D. Mehrabi


In a geometric k-clustering problem the goal is to partition a set of n points S in R^d into k subsets such that a certain cost function of the clustering is minimized. We present a general method to compute a small coreset R of size independent of n such that the cost of a k-clustering of R is a (1+eps)-approximation to the cost of k-clustering of S. Our method applies to a large class of clustering problems, including k-center clustering in any Lp-metric. Our algorithm has a linear running time for a fixed k.

Best Laid Plans of Lions and Men

Eva Rotenberg (DIKU)

Joint work with: Mikkel Abrahamsen, Jacob Holm, Christian Wulff-Nilsen


We answer the following question dating back to J.E. Littlewood (1885--1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assumed to be points moving with at most unit speed. That the lakes are rectifiable means that their boundaries are finitely long. This requirement is to avoid pathological examples where the man survives forever because any path to the lions is infinitely long. We show that the answer to the question is not always "yes", by giving an example of a region $R$ in the plane where the man has a strategy to survive forever. $R$ is a polygonal region with holes and the exterior and interior boundaries are pairwise disjoint, simple polygons. Our construction is the first truly two-dimensional example where the man can survive.

We prove tightness in the sense that three lions can catch a man in a region with finitely many polygonal lakes.

Finally, we consider the following game played on the entire plane instead of a bounded area: There is any finite number of unit speed lions and one fast man who can run with speed 1+epsilon for some value epsilon>0. Can the man always survive? We answer the question in the affirmative for any constant epsilon>0.

Minimum Perimeter-Sum Partitions in the Plane

Mikkel Abrahamsen (DIKU)

Joint work with: Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi


Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P1 and P2 such that the sum of the perimeters of CH(P1) and CH(P2) is minimized, where CH(Pi) denotes the convex hull of Pi.

The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n²) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log ⁴ n) time and a (1+epsilon)-approximation algorithm running in O(n + 1/epsilon² · \log⁴(1/epsilon)) time.

Irrational Guards are Sometimes Needed

Anna Adamaszek (DIKU)

Joint work with: Mikkel Abrahamsen, Tillmann Miltzow


We study the art gallery problem, which is one of the fundamental problems in computational geometry. 

The objective is to place a minimum number of guards inside a simple polygon so that the guards together can see the whole polygon. 

We say that a guard at position x sees a point y if the line segment xy is contained in the polygon.

Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. 

We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. 

Otherwise, four guards are needed. By extending this example, we show that for every n, there is a polygon which can be guarded by 3n guards with irrational coordinates but needs 4n guards if the coordinates have to be rational.

Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.