16 June 2017

Mikkel Abrahamsen gets four papers accepted at SoCG

Top conference

DIKU's PhD student Mikkel Abrahamsen is the first researcher in Denmark, who gets four papers accepted the same year at Symposium on Computational Geometry (SoCG). And he is the researcher with the highest number of papers accepted this year. SoCG is the top conference in algorithmic geometry and will take place in Brisbane, Australia on 4-7 July this year.

Mikkel Abrahamsen has a bachelor degree in Mathematics and a master degree in Computer Science from DIKU. Today, he is a PhD student in DIKUs Algorithm and Programming Languages section. His four accepted papers at SoCG are all dealing with different kinds of algorithmic geometry problems.

The solution to a 40 year old mathematical problem

One of the papers is about “the lion and man problem” and is written in collaboration with Jacob Holm, Eva Rotenberg and Christian Wulff-Nilsen. In the article they solve a 40 year old mathematical problem by proving that two lions not always are enough to catch a man in a bounded area with rectifiable lakes.

The other paper is written together with Anna Adamaszek and Tillmann Miltzow, and they study the art gallery problem, which is one of the fundamental problems in computational geometry.

The last two papers are written with four researchers from Eindhoven University of Technology, where Mikkel studied a year ago during his exchange. Those articles are about different kinds of clustering problem for points in a set.

The four articles

Best Laid Plans of Lions and Men

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg og Christian Wulff-Nielsen.

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.

Next, 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 + e for some value e > 0. Can the man always survive? We answer the question in the affirmative for any constant e > 0.

Irrational Guards are Sometimes Needed

Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow

In this paper 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.

Range-Clustering Queries

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi.

In a geometric k-clustering problem the goal is to partition a set of points in Rd into k subsets such that a certain cost function of the clustering is minimized. We present data structures for orthogonal range-clustering queries on a point set S: given a query box Q and integer k > 2, compute an optimal k-clustering for the points in the intersection of S and Q. We obtain the following results. We present a general method to compute a (1+e)-approximation to a range-clustering query, where e > 0 is a parameter that can be specified as part of the query. Our method applies to a large class of clustering problems, including k-center clustering in any Lp-metric and a variant of k-center clustering where the goal is to minimize the sum (instead of maximum) of the cluster sizes. We extend our method to deal with capacitated k-clustering problems, where each of the clusters should not contain more than a given number of points. For the special cases of rectilinear k-center clustering in R1, and in R2 for k = 2, 3, we present data structures that answer range-clustering queries exactly.

Minimum Perimeter-Sum Partitions in the Plane

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and 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(n2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an algorithm solving the problem in O(n log4 n) time and a (1 + e)-approximation algorithm for the same problem running in O(n + 1/e2 · log4(1/e)) time.