Search Results

Documents authored by Abrahamsen, Mikkel

Document
DOI: 10.4230/LIPIcs.ESA.2024.5
Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional

Authors: Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, and László Kozma

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In the online sorting problem, n items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size-n array. The goal is to minimize the sum of absolute differences between items in consecutive cells. This natural problem was recently introduced by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) as a tool in their study of online geometric packing problems. They showed that when the items are reals from the interval [0,1] a competitive ratio of O(√n) is achievable, and no deterministic algorithm can improve this ratio asymptotically. In this paper, we extend and generalize the study of online sorting in three directions: - randomized: we settle the open question of Aamand et al. by showing that the O(√n) competitive ratio for the online sorting of reals cannot be improved even with the use of randomness; - stochastic: we consider inputs consisting of n samples drawn uniformly at random from an interval, and give an algorithm with an improved competitive ratio of Õ(n^{1/4}). The result reveals connections between online sorting and the design of efficient hash tables; - high-dimensional: we show that Õ(√n)-competitive online sorting is possible even for items from ℝ^d, for arbitrary fixed d, in an adversarial model. This can be viewed as an online variant of the classical TSP problem where tasks (cities to visit) are revealed one by one and the salesperson assigns each task (immediately and irrevocably) to its timeslot. Along the way, we also show a tight O(log n)-competitiveness result for uniform metrics, i.e., where items are of different types and the goal is to order them so as to minimize the number of switches between consecutive items of different types.
Cite as

Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, and László Kozma. Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ESA.2024.5,
  author =	{Abrahamsen, Mikkel and Bercea, Ioana O. and Beretta, Lorenzo and Klausen, Jonas and Kozma, L\'{a}szl\'{o}},
  title =	{{Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.5},
  URN =		{urn:nbn:de:0030-drops-210766},
  doi =		{10.4230/LIPIcs.ESA.2024.5},
  annote =	{Keywords: sorting, online algorithm, TSP}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.2
Clustering with Few Disks to Minimize the Sum of Radii

Authors: Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm [GKKPV '12]; however, the running time of this algorithm is 𝒪(n^881), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time 𝒪(n² log² n log² log n) was given over 30 years ago [Eppstein '92]. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected 𝒪(n log² n log² log n) time. We generalize this result to any constant dimension d, for which we give an 𝒪(n^{2-1/(⌈d/2⌉ + 1) + ε}) time algorithm. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane that runs in expected 𝒪(n² log² n log² log n) time. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining clusters in an optimal solution.
Cite as

Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous. Clustering with Few Disks to Minimize the Sum of Radii. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2024.2,
  author =	{Abrahamsen, Mikkel and de Berg, Sarita and Meijer, Lucas and Nusser, Andr\'{e} and Theocharous, Leonidas},
  title =	{{Clustering with Few Disks to Minimize the Sum of Radii}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.2},
  URN =		{urn:nbn:de:0030-drops-199472},
  doi =		{10.4230/LIPIcs.SoCG.2024.2},
  annote =	{Keywords: geometric clustering, minimize sum of radii, covering points with disks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.1
Geometric Embeddability of Complexes Is ∃ℝ-Complete

Authors: Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝ^d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d-1,d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.
Cite as

Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric Embeddability of Complexes Is ∃ℝ-Complete. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.1,
  author =	{Abrahamsen, Mikkel and Kleist, Linda and Miltzow, Tillmann},
  title =	{{Geometric Embeddability of Complexes Is \exists\mathbb{R}-Complete}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.1},
  URN =		{urn:nbn:de:0030-drops-178518},
  doi =		{10.4230/LIPIcs.SoCG.2023.1},
  annote =	{Keywords: simplicial complex, geometric embedding, linear embedding, hypergraph, recognition, existential theory of the reals}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.2
Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

Authors: Mikkel Abrahamsen and Bartosz Walczak

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes G^{hom}(A) and G^{sim}(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that G^{hom}(A) = G^{hom}(B) if and only if A and B are affine equivalent, and G^{sim}(A) = G^{sim}(B) if and only if A and B are similar.
Cite as

Mikkel Abrahamsen and Bartosz Walczak. Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.2,
  author =	{Abrahamsen, Mikkel and Walczak, Bartosz},
  title =	{{Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.2},
  URN =		{urn:nbn:de:0030-drops-178523},
  doi =		{10.4230/LIPIcs.SoCG.2023.2},
  annote =	{Keywords: geometric intersection graph, convex disk, homothet, similarity}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2023.66
Constructing Concise Convex Covers via Clique Covers (CG Challenge)

Authors: Mikkel Abrahamsen, William Bille Meyling, and André Nusser

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
This work describes the winning implementation of the CG:SHOP 2023 Challenge. The topic of the Challenge was the convex cover problem: given a polygon P (with holes), find a minimum-cardinality set of convex polygons whose union equals P. We use a three-step approach: (1) Create a suitable partition of P. (2) Compute a visibility graph of the pieces of the partition. (3) Solve a vertex clique cover problem on the visibility graph, from which we then derive the convex cover. This way we capture the geometric difficulty in the first step and the combinatorial difficulty in the third step.
Cite as

Mikkel Abrahamsen, William Bille Meyling, and André Nusser. Constructing Concise Convex Covers via Clique Covers (CG Challenge). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.66,
  author =	{Abrahamsen, Mikkel and Bille Meyling, William and Nusser, Andr\'{e}},
  title =	{{Constructing Concise Convex Covers via Clique Covers}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{66:1--66:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.66},
  URN =		{urn:nbn:de:0030-drops-179164},
  doi =		{10.4230/LIPIcs.SoCG.2023.66},
  annote =	{Keywords: Convex cover, Polygons with holes, Algorithm engineering, Vertex clique cover}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.1
Tiling with Squares and Packing Dominos in Polynomial Time

Authors: Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
A polyomino is a polygonal region with axis-parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container P. We give polynomial-time algorithms for deciding if P can be tiled with k× k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k× k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2× 1 dominos, allowing rotations by 90^∘. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2× 1 dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2× 2 squares is known to be NP-hard [J. Algorithms 1990]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P. However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple O(nlog n)-time algorithm for tiling with squares, where n is the number of corners of P. We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O(n³) vertices. This leads to algorithms with running times O(n³(log³ n)/(log²log n)) and O(n³(log² n)/(log log n)), respectively.
Cite as

Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen. Tiling with Squares and Packing Dominos in Polynomial Time. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2022.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Ahle, Thomas and Rasmussen, Peter M. R.},
  title =	{{Tiling with Squares and Packing Dominos in Polynomial Time}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.1},
  URN =		{urn:nbn:de:0030-drops-160096},
  doi =		{10.4230/LIPIcs.SoCG.2022.1},
  annote =	{Keywords: packing, tiling, polyominos}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.3
Classifying Convex Bodies by Their Contact and Intersection Graphs

Authors: Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Let A be a convex body in the plane and A₁,…,A_n be translates of A. Such translates give rise to an intersection graph of A, G = (V,E), with vertices V = {1,… ,n} and edges E = {uv∣ A_u ∩ A_v ≠ ∅}. The subgraph G' = (V, E') satisfying that E' ⊂ E is the set of edges uv for which the interiors of A_u and A_v are disjoint is a unit distance graph of A. If furthermore G' = G, i.e., if the interiors of A_u and A_v are disjoint whenever u≠ v, then G is a contact graph of A. In this paper, we study which pairs of convex bodies have the same contact, unit distance, or intersection graphs. We say that two convex bodies A and B are equivalent if there exists a linear transformation B' of B such that for any slope, the longest line segments with that slope contained in A and B', respectively, are equally long. For a broad class of convex bodies, including all strictly convex bodies and linear transformations of regular polygons, we show that the contact graphs of A and B are the same if and only if A and B are equivalent. We prove the same statement for unit distance and intersection graphs.
Cite as

Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen. Classifying Convex Bodies by Their Contact and Intersection Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2021.3,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Knudsen, Jakob B{\ae}k Tejs and Rasmussen, Peter Michael Reichstein},
  title =	{{Classifying Convex Bodies by Their Contact and Intersection Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.3},
  URN =		{urn:nbn:de:0030-drops-138024},
  doi =		{10.4230/LIPIcs.SoCG.2021.3},
  annote =	{Keywords: convex body, contact graph, intersection graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.5
Chasing Puppies: Mobile Beacon Routing on Closed Curves

Authors: Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
Cite as

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5,
  author =	{Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
  title =	{{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.5},
  URN =		{urn:nbn:de:0030-drops-138046},
  doi =		{10.4230/LIPIcs.SoCG.2021.5},
  annote =	{Keywords: Beacon routing, navigation, generic smooth curves, puppies}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.6
Online Packing to Minimize Area or Perimeter

Authors: Mikkel Abrahamsen and Lorenzo Beretta

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We consider online packing problems where we get a stream of axis-parallel rectangles. The rectangles have to be placed in the plane without overlapping, and each rectangle must be placed without knowing the subsequent rectangles. The goal is to minimize the perimeter or the area of the axis-parallel bounding box of the rectangles. We either allow rotations by 90^∘ or translations only. For the perimeter version we give algorithms with an absolute competitive ratio slightly less than 4 when only translations are allowed and when rotations are also allowed. We then turn our attention to minimizing the area and show that the competitive ratio of any algorithm is at least Ω(√n), where n is the number of rectangles in the stream, and this holds with and without rotations. We then present algorithms that match this bound in both cases and the competitive ratio is thus optimal to within a constant factor. We also show that the competitive ratio cannot be bounded as a function of Opt. We then consider two special cases. The first is when all the given rectangles have aspect ratios bounded by some constant. The particular variant where all the rectangles are squares and we want to minimize the area of the bounding square has been studied before and an algorithm with a competitive ratio of 8 has been given [Fekete and Hoffmann, Algorithmica, 2017]. We improve the analysis of the algorithm and show that the ratio is at most 6, which is tight. The second special case is when all edges have length at least 1. Here, the Ω(√n) lower bound still holds, and we turn our attention to lower bounds depending on Opt. We show that any algorithm for the translational case has a competitive ratio of at least Ω(√{Opt}). If rotations are allowed, we show a lower bound of Ω(∜{Opt}). For both versions, we give algorithms that match the respective lower bounds: With translations only, this is just the algorithm from the general case with competitive ratio O(√n) = O(√{Opt}). If rotations are allowed, we give an algorithm with competitive ratio O(min{√n,∜{Opt}}), thus matching both lower bounds simultaneously.
Cite as

Mikkel Abrahamsen and Lorenzo Beretta. Online Packing to Minimize Area or Perimeter. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.6,
  author =	{Abrahamsen, Mikkel and Beretta, Lorenzo},
  title =	{{Online Packing to Minimize Area or Perimeter}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.6},
  URN =		{urn:nbn:de:0030-drops-138054},
  doi =		{10.4230/LIPIcs.SoCG.2021.6},
  annote =	{Keywords: Packing, online algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.9
Geometric Multicut

Authors: Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2-4/3k)-approximation algorithm.
Cite as

Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric Multicut. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ICALP.2019.9,
  author =	{Abrahamsen, Mikkel and Giannopoulos, Panos and L\"{o}ffler, Maarten and Rote, G\"{u}nter},
  title =	{{Geometric Multicut}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.9},
  URN =		{urn:nbn:de:0030-drops-105850},
  doi =		{10.4230/LIPIcs.ICALP.2019.9},
  annote =	{Keywords: multicut, clustering, Steiner tree}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.128
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Authors: Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. We give upper and lower bounds for the size of induced universal graphs for the family of graphs with n vertices of maximum degree D. Our new bounds improve several previous results except for the special cases where D is either near-constant or almost n/2. For constant even D Butler [Graphs and Combinatorics 2009] has shown O(n^(D/2)) and recently Alon and Nenadov [SODA 2017] showed the same bound for constant odd D. For constant D Butler also gave a matching lower bound. For generals graphs, which corresponds to D = n, Alon [Geometric and Functional Analysis, to appear] proved the existence of an induced universal graph with (1+o(1)) \cdot 2^((n-1)/2) vertices, leading to a smaller constant than in the previously best known bound of 16 * 2^(n/2) by Alstrup, Kaplan, Thorup, and Zwick [STOC 2015]. In this paper we give the following lower and upper bound of binom(floor(n/2))(floor(D/2)) * n^(-O(1)) and binom(floor(n/2))(floor(D/2)) * 2^(O(sqrt(D log D) * log(n/D))), respectively, where the upper bound is the main contribution. The proof that it is an induced universal graph relies on a randomized argument. We also give a deterministic upper bound of O(n^k / (k-1)!). These upper bounds are the best known when D <= n/2 - tilde-Omega(n^(3/4)) and either D is even and D = omega(1) or D is odd and D = omega(log n/log log n). In this range we improve asymptotically on the previous best known results by Butler [Graphs and Combinatorics 2009], Esperet, Arnaud and Ochem [IPL 2008], Adjiashvili and Rotbart [ICALP 2014], Alon and Nenadov [SODA 2017], and Alon [Geometric and Functional Analysis, to appear].
Cite as

Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 128:1-128:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ICALP.2017.128,
  author =	{Abrahamsen, Mikkel and Alstrup, Stephen and Holm, Jacob and Knudsen, Mathias B{\ae}k Tejs and St\"{o}ckel, Morten},
  title =	{{Near-Optimal Induced Universal Graphs for Bounded Degree Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{128:1--128:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.128},
  URN =		{urn:nbn:de:0030-drops-74114},
  doi =		{10.4230/LIPIcs.ICALP.2017.128},
  annote =	{Keywords: Adjacency labeling schemes, Bounded degree graphs, Induced universal graphs, Distributed computing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.3
Irrational Guards are Sometimes Needed

Authors: Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
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.
Cite as

Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational Guards are Sometimes Needed. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.3,
  author =	{Abrahamsen, Mikkel and Adamaszek, Anna and Miltzow, Tillmann},
  title =	{{Irrational Guards are Sometimes Needed}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.3},
  URN =		{urn:nbn:de:0030-drops-71946},
  doi =		{10.4230/LIPIcs.SoCG.2017.3},
  annote =	{Keywords: art gallery problem, computational geometry, irrational numbers}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.4
Minimum Perimeter-Sum Partitions in the Plane

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

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P_1 and P_2 such that the sum of the perimeters of CH(P_1) and CH(P_2) 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^2) 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^4 n) time and a (1+e)-approximation algorithm running in O(n + 1/e^2 log^4(1/e)) time.
Cite as

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Minimum Perimeter-Sum Partitions in the Plane. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.4,
  author =	{Abrahamsen, Mikkel and de Berg, Mark and Buchin, Kevin and Mehr, Mehran and Mehrabi, Ali D.},
  title =	{{Minimum Perimeter-Sum Partitions in the Plane}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.4},
  URN =		{urn:nbn:de:0030-drops-72048},
  doi =		{10.4230/LIPIcs.SoCG.2017.4},
  annote =	{Keywords: Computational geometry, clustering, minimum-perimeter partition, convex hull}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.5
Range-Clustering Queries

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

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
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 an integer k > 2, compute an optimal k-clustering for the subset of S inside Q. We obtain the following results. * We present a general method to compute a (1+epsilon)-approximation to a range-clustering query, where epsilon>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 R^1, and in R^2 for k = 2 or 3, we present data structures that answer range-clustering queries exactly.
Cite as

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Range-Clustering Queries. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.5,
  author =	{Abrahamsen, Mikkel and de Berg, Mark and Buchin, Kevin and Mehr, Mehran and Mehrabi, Ali D.},
  title =	{{Range-Clustering Queries}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.5},
  URN =		{urn:nbn:de:0030-drops-72147},
  doi =		{10.4230/LIPIcs.SoCG.2017.5},
  annote =	{Keywords: Geometric data structures, clustering, k-center problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.6
Best Laid Plans of Lions and Men

Authors: Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
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+epsilon for some value epsilon>0. Can the man always survive? We answer the question in the affirmative for any constant epsilon>0.
Cite as

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Best Laid Plans of Lions and Men. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.6,
  author =	{Abrahamsen, Mikkel and Holm, Jacob and Rotenberg, Eva and Wulff-Nilsen, Christian},
  title =	{{Best Laid Plans of Lions and Men}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.6},
  URN =		{urn:nbn:de:0030-drops-72053},
  doi =		{10.4230/LIPIcs.SoCG.2017.6},
  annote =	{Keywords: Lion and man game, Pursuit evasion game, Winning strategy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.4
Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace

Authors: Mikkel Abrahamsen and Bartosz Walczak

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We describe the first algorithm to compute the outer common tangents of two disjoint simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies on the same side of the line. An outer common tangent of two polygons is a tangent of both polygons such that the polygons lie on the same side of the tangent. Each polygon is given as a read-only array of its corners in cyclic order. The algorithm detects if an outer common tangent does not exist, which is the case if and only if the convex hull of one of the polygons is contained in the convex hull of the other. Otherwise, two corners defining an outer common tangent are returned.
Cite as

Mikkel Abrahamsen and Bartosz Walczak. Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ESA.2016.4,
  author =	{Abrahamsen, Mikkel and Walczak, Bartosz},
  title =	{{Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.4},
  URN =		{urn:nbn:de:0030-drops-63465},
  doi =		{10.4230/LIPIcs.ESA.2016.4},
  annote =	{Keywords: simple polygon, common tangent, optimal algorithm, constant workspace}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.4
Finding the Maximum Subset with Bounded Convex Curvature

Authors: Mikkel Abrahamsen and Mikkel Thorup

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When machining a pocket in a solid piece of material such as steel using a rough tool in a milling machine, sharp convex corners of the pocket cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a tool path that maximizes the use of the rough tool. Mathematically, this boils down to the following problem. Given a simply-connected set of points P in the plane such that the boundary of P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q of P consisting of simply-connected sets where the boundary of each set is a curve with bounded convex curvature. A closed curve has bounded convex curvature if, when traversed in counterclockwise direction, it turns to the left with curvature at most 1. There is no bound on the curvature where it turns to the right. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of the pocket. We devise an algorithm to compute the unique maximum such set Q. The algorithm runs in O(n log n) time and uses O(n) space. For the correctness of our algorithm, we prove a new generalization of the Pestov-Ionin Theorem. This is needed to show that the output Q of our algorithm is indeed maximum in the sense that if Q' is any subset of P with a boundary of bounded convex curvature, then Q' is a subset of Q.
Cite as

Mikkel Abrahamsen and Mikkel Thorup. Finding the Maximum Subset with Bounded Convex Curvature. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2016.4,
  author =	{Abrahamsen, Mikkel and Thorup, Mikkel},
  title =	{{Finding the Maximum Subset with Bounded Convex Curvature}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.4},
  URN =		{urn:nbn:de:0030-drops-58960},
  doi =		{10.4230/LIPIcs.SoCG.2016.4},
  annote =	{Keywords: planar computational geometry, bounded curvature, pocket machining}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.5
Graph Reconstruction with a Betweenness Oracle

Authors: Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Graph reconstruction algorithms seek to learn a hidden graph by repeatedly querying a black-box oracle for information about the graph structure. Perhaps the most well studied and applied version of the problem uses a distance oracle, which can report the shortest path distance between any pair of nodes. We introduce and study the betweenness oracle, where bet(a, m, z) is true iff m lies on a shortest path between a and z. This oracle is strictly weaker than a distance oracle, in the sense that a betweenness query can be simulated by a constant number of distance queries, but not vice versa. Despite this, we are able to develop betweenness reconstruction algorithms that match the current state of the art for distance reconstruction, and even improve it for certain types of graphs. We obtain the following algorithms: (1) Reconstruction of general graphs in O(n^2) queries, (2) Reconstruction of degree-bounded graphs in ~O(n^{3/2}) queries, (3) Reconstruction of geodetic degree-bounded graphs in ~O(n) queries In addition to being a fundamental graph theoretic problem with some natural applications, our new results shed light on some avenues for progress in the distance reconstruction problem.
Cite as

Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. Graph Reconstruction with a Betweenness Oracle. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.STACS.2016.5,
  author =	{Abrahamsen, Mikkel and Bodwin, Greg and Rotenberg, Eva and St\"{o}ckel, Morten},
  title =	{{Graph Reconstruction with a Betweenness Oracle}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.5},
  URN =		{urn:nbn:de:0030-drops-57068},
  doi =		{10.4230/LIPIcs.STACS.2016.5},
  annote =	{Keywords: graph reconstruction, bounded degree graphs, query complexity}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.198
An Optimal Algorithm for the Separating Common Tangents of Two Polygons

Authors: Mikkel Abrahamsen

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We describe an algorithm for computing the separating common tangents of two simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies to the same side of the line. A separating common tangent of two polygons is a tangent of both polygons where the polygons are lying on different sides of the tangent. Each polygon is given as a read-only array of its corners. If a separating common tangent does not exist, the algorithm reports that. Otherwise, two corners defining a separating common tangent are returned. The algorithm is simple and implies an optimal algorithm for deciding if the convex hulls of two polygons are disjoint or not. This was not known to be possible in linear time and constant workspace prior to this paper. An outer common tangent is a tangent of both polygons where the polygons are on the same side of the tangent. In the case where the convex hulls of the polygons are disjoint, we give an algorithm for computing the outer common tangents in linear time using constant workspace.
Cite as

Mikkel Abrahamsen. An Optimal Algorithm for the Separating Common Tangents of Two Polygons. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 198-208, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{abrahamsen:LIPIcs.SOCG.2015.198,
  author =	{Abrahamsen, Mikkel},
  title =	{{An Optimal Algorithm for the Separating Common Tangents of Two Polygons}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{198--208},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.198},
  URN =		{urn:nbn:de:0030-drops-51313},
  doi =		{10.4230/LIPIcs.SOCG.2015.198},
  annote =	{Keywords: planar computational geometry, simple polygon, common tangent, optimal algorithm, constant workspace}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact