Mikkel Abrahamsen får fire artikler accepteret ved SoCG

Mikkel Abrahamsen har en bachelor i Matematik og en kandidat i Datalogi fra DIKU, og er i dag ph.d.-studerende i DIKUs Algorithm and Programming Languages sektion. Det er som ph.d.-studerende, at Mikkel har fået accepteret de fire artikler om forskellige algoritimisk geometriske problemer ved SoCG-konferencen.

40 år gammelt matematisk problem er løst

Den ene artikel handler om løve-og-mand-problemet og er lavet sammen med Jacob Holm, Eva Rotenberg og Christian Wulff-Nilsen. I artiklen løser de et over 40 år gammelt matematisk problem ved at vise, at to løver ikke altid er nok til at fange en mand i et begrænset område med søer.

Den anden artikel har Mikkel lavet sammen med Anna Adamaszek og Tillmann Miltzow, og i den besvarer de et åbent spørgsmål inden for "the art gallery problem", som er et af de klassiske problemer i algoritmisk geometri.

De to sidste artikler er lavet med fire forskere fra Eindhoven University of Technology, som Mikkel besøgte for et år siden på sit udlandsophold. De handler om forskellige clustering-problemer for punkter i planen.

De fire artikler

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 og 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 R^d 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 L_p-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 R¹, and in R² 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 P₁ and P₂ such that the sum of the perimeters of ch(P₁) and ch(P₂) is minimized, where ch(P_i) denotes the convex hull of P_i. 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 algorithm solving the problem in O(n log⁴ n) time and a (1 + e)-approximation algorithm for the same problem running in O(n + 1/e² · log⁴(1/e)) time.