Mikkel Abrahamsen

Search results

• 2025

  Geometric Embeddability of Complexes is ∃ℝ-complete

  Abrahamsen, M., Kleist, L. & Miltzow, T., 2025, In: Journal of the ACM. 72, 1, 26 p., 9.

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  3 Downloads (Pure)

• Partitioning a Polygon Into Small Pieces

  Abrahamsen, M. & Rasmussen, N. L., 2025, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Azar, Y. & Panigrahi, D. (eds.). Society for Industrial and Applied Mathematics, p. 3562-3589

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  File
  3 Downloads (Pure)
• 2024

  Clustering with Few Disks to Minimize the Sum of Radii

  Abrahamsen, M., de Berg, S., Meijer, L., Nusser, A. & Theocharous, L., 2024, In: Leibniz International Proceedings in Informatics, LIPIcs. 293, 15 p., 2.

  Research output: Contribution to journal › Conference article › Research › peer-review

  Open Access

  File
  1 Citation (Scopus)

  3 Downloads (Pure)

• ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting

  Abrahamsen, M., 2024, In: S I G A C T News. 55, 4, p. 108-111

  Research output: Contribution to journal › Journal article › Research › peer-review

  File

• Framework for ∃R-Completeness of Two-Dimensional Packing Problems

  Abrahamsen, M., Miltzow, T. & Seiferth, N., 2024, In: TheoretiCS. 3, p. 1-78 11.

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  2 Downloads (Pure)

• Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

  Abrahamsen, M. & Stade, J., 2024, Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024. IEEE Computer Society Press, p. 1355-1371 17 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  13 Downloads (Pure)

• Minimum Star Partitions of Simple Polygons in Polynomial Time

  Abrahamsen, M., Blikstad, J., Nusser, A. & Zhang, H., 2024, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Mohar, B., Shinkar, I. & O�Donnell, R. (eds.). Association for Computing Machinery, p. 904-910 7 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  4 Downloads (Pure)

• Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional

  Abrahamsen, M., Bercea, I. O., Beretta, L., Klausen, J. & Kozma, L., 2024, In: Leibniz International Proceedings in Informatics, LIPIcs. 308, 15 p., 5.

  Research output: Contribution to journal › Conference article › Research › peer-review

  Open Access

  File
  12 Downloads (Pure)
• 2023

  Constructing Concise Convex Covers via Clique Covers

  Abrahamsen, M., Meyling, W. B. & Nusser, A., 2023, 39th International Symposium on Computational Geometry, SoCG 2023. Chambers, E. W. & Gudmundsson, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-9 66. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  2 Citations (Scopus)

  34 Downloads (Pure)

• Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity

  Abrahamsen, M., Geft, T., Halperin, D. & Ugav, B., 2023, AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. Association for Computing Machinery, p. 932-940

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  2 Citations (Scopus)

  16 Downloads (Pure)

• Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

  Abrahamsen, M. & Walczak, B., 2023, 39th International Symposium on Computational Geometry, SoCG 2023. Chambers, E. W. & Gudmundsson, J. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-16 2. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  20 Downloads (Pure)

• Geometric Embeddability of Complexes Is ∃R-Complete

  Abrahamsen, M., Kleist, L. & Miltzow, T., 2023, 39th International Symposium on Computational Geometry, SoCG 2023. Chambers, E. W. & Gudmundsson, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 1. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  25 Downloads (Pure)

• How to Cut Corners and Get Bounded Convex Curvature

  Abrahamsen, M. & Thorup, M., 2023, In: Discrete and Computational Geometry. 69, p. 1195–1231,

  Research output: Contribution to journal › Journal article › Research › peer-review

  File
  1 Citation (Scopus)

  7 Downloads (Pure)

• Online Sorting and Translational Packing of Convex Polygons

  Aamand, A., Abrahamsen, M., Beretta, L. & Kleist, L., 2023, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Bansal, N. & Nagarajan, V. (eds.). Society for Industrial and Applied Mathematics, p. 1806-1833

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  File
  2 Citations (Scopus)

  5 Downloads (Pure)

• Tiling with Squares and Packing Dominos in Polynomial Time

  Aamand, A., Abrahamsen, M., Rasmussen, P. M. R. & Ahle, T. D., 2023, In: ACM Transactions on Algorithms. 19, 3, p. 1-28 30.

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  2 Citations (Scopus)

  13 Downloads (Pure)
• 2022

  Chasing Puppies: Mobile Beacon Routing on Closed Curves

  Abrahamsen, M., Erickson, J., Kostitsyna, I., Löffler, M., Miltzow, T., Urhausen, J., Vermeulen, J. & Viglietta, G., 2022, In: Journal of Computational Geometry. 13, 2, p. 115-150

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  14 Downloads (Pure)

• Covering Polygons is Even Harder

  Abrahamsen, M., 2022, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 375-386

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  File
  18 Citations (Scopus)

  19 Downloads (Pure)

• The Art Gallery Problem is ∃ℝ-complete

  Abrahamsen, M., Adamaszek, A. & Miltzow, T., 28 Feb 2022, In: Journal of the ACM. 69, 1, p. 1-70 4.

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  27 Citations (Scopus)

  19 Downloads (Pure)

• Tiling with Squares and Packing Dominos in Polynomial Time

  Aamand, A., Abrahamsen, M., Ahle, T. & Rasmussen, P. M. R., 2022, 38th International Symposium on Computational Geometry, SoCG 2022. Goaoc, X. & Kerber, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 1. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 224).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  1 Citation (Scopus)

  26 Downloads (Pure)
• 2021

  Chasing puppies: Mobile beacon routing on closed curves

  Abrahamsen, M., Erickson, J., Kostitsyna, I., Löffler, M., Miltzow, T., Urhausen, J., Vermeulen, J. & Viglietta, G., 2021, 37th International Symposium on Computational Geometry, SoCG 2021. Buchin, K. & de Verdiere, E. C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 19 p. 5. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 189).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  19 Downloads (Pure)

• Classifying convex bodies by their contact and intersection graphs

  Aamand, A., Abrahamsen, M., Knudsen, J. B. T. & Rasmussen, P. M. R., 2021, 37th International Symposium on Computational Geometry, SoCG 2021. Buchin, K. & de Verdiere, E. C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 16 p. 3. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 189).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  2 Citations (Scopus)

  48 Downloads (Pure)

• Online packing to minimize area or perimeter

  Abrahamsen, M. & Beretta, L., 2021, 37th International Symposium on Computational Geometry, SoCG 2021. Buchin, K. & de Verdiere, E. C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 15 p. 6. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 189).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  1 Citation (Scopus)

  58 Downloads (Pure)
• 2020

  Disks in Curves of Bounded Convex Curvature

  Aamand, A., Abrahamsen, M. & Thorup, M., 2020, In: American Mathematical Monthly. 127, 7, p. 579-593 15 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  24 Downloads (Pure)

• Escaping an Infinitude of Lions

  Abrahamsen, M., Holm, J., Rotenberg, E. & Wulff-nilsen, C., 2020, In: The American Mathematical Monthly. 127, 10, p. 880-896

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  33 Downloads (Pure)

• Framework for er-completeness of two-dimensional packing problems

  Abrahamsen, M., Miltzow, T. & Seiferth, N., 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society Press, p. 1014-1021 9317895

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
  27 Citations (Scopus)

• Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane

  Abrahamsen, M., Giannopoulos, P., Löffler, M. & Rote, G., 2020, In: Discrete & Computational Geometry. 64, p. 575–607

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  26 Downloads (Pure)

• Minimum perimeter-sum partitions in the plane

  Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M. & Mehrabi, A. D., 2020, In: Discrete & Computational Geometry. 63, p. 483–505

  Research output: Contribution to journal › Journal article › Research › peer-review
  1 Citation (Scopus)

• Near-optimal induced universal graphs for cycles and paths

  Abrahamsen, M., Alstrup, S., Holm, J., Knudsen, M. B. T. & Stöckel, M., 2020, In: Discrete Applied Mathematics. 282, p. 1-13 13 p.

  Research output: Contribution to journal › Journal article › Research › peer-review
  1 Citation (Scopus)
• 2019

  Geometric multicut

  Abrahamsen, M., Giannopoulos, P., Löffler, M. & Rote, G., 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Baier, C., Chatzigiannakis, I., Flocchini, P. & Leonardi, S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 15 p. 9. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  2 Citations (Scopus)

  25 Downloads (Pure)

• Spiral tool paths for high-speed machining of 2D pockets with or without islands

  Abrahamsen, M., 1 Jan 2019, In: Journal of Computational Design and Engineering. 6, 1, p. 105-117

  Research output: Contribution to journal › Journal article › Research › peer-review

  Open Access

  File
  12 Citations (Scopus)

  263 Downloads (Pure)
• 2018

  Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

  Abrahamsen, M. & Walczak, B., Dec 2018, In: ACM Transactions on Algorithms. 15, 1, p. 1-21 12.

  Research output: Contribution to journal › Journal article › Research › peer-review
  2 Citations (Scopus)

• Fast fencing

  Abrahamsen, M., Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., Roytman, A. & Thorup, M., 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, p. 564-573

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
  5 Citations (Scopus)

• The art gallery problem is ∃ ℝ-complete

  Abrahamsen, M., Adamaszek, A. & Miltzow, T., 2018, STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, p. 65-73

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
  35 Citations (Scopus)
• 2017

  Best laid plans of lions and men

  Abrahamsen, M., Holm, J., Rotenberg, E. & Wulff-Nilsen, C., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017). Aronov, B. & Katz, M. J. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16 p. 6. (Leibniz International Proceedings in Informatics, Vol. 77).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  2 Citations (Scopus)

  160 Downloads (Pure)

• Irrational Guards are Sometimes Needed

  Abrahamsen, M., Adamaszek, A. & Miltzow, T., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017). Aronov, B. & Katz, M. J. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-15 3. (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 77).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  12 Citations (Scopus)

  121 Downloads (Pure)

• Minimum perimeter-sum partitions in the plane

  Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M. & Mehrabi, A. D., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017). Aronov, B. & Katz, M. J. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15 p. 4. (Leibniz International Proceedings in Informatics, Vol. 77).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  4 Citations (Scopus)

  104 Downloads (Pure)

• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

  Abrahamsen, M., Alstrup, S., Holm, J., Knudsen, M. B. T. & Stöckel, M., 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 201. Chatzigiannaki, I., Indyk, P., Kuhn, F. & Muscholl, A. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-14 128. (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 80).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  95 Downloads (Pure)

• New results on classical problems in computational geometry in the plane

  Abrahamsen, M., 2017, Department of Computer Science, Faculty of Science, University of Copenhagen.

  Research output: Book/Report › Ph.D. thesis

  File

• Range-clustering queries

  Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M. & Mehrabi, A. D., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017). Aronov, B. & Katz, M. J. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16 p. 5. (Leibniz International Proceedings in Informatics, Vol. 77).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  33 Downloads (Pure)
• 2016

  Finding the maximum subset with bounded convex curvature

  Abrahamsen, M. & Thorup, M., 2016, 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17 p. 4. (Leibniz International Proceedings in Informatics, Vol. 51).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  125 Downloads (Pure)

• Graph reconstruction with a betweenness oracle

  Abrahamsen, M., Bodwin, G., Rotenberg, E. & Stöckel, M. D., 2016, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Ollinger, N. & Vollmer, H. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 5:1-5:14 14 p. 5. (Leibniz International Proceedings in Informatics, Vol. 47).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  11 Citations (Scopus)

  207 Downloads (Pure)

• Outer common tangents and nesting of convex hulls in linear time and constant workspace

  Abrahamsen, M. & Walczak, B., 2016, 24th Annual European Symposium on Algorithms (ESA 2016). Sankowski, P. & Zaroliagis, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15 p. 4. (Leibniz International Proceedings in Informatics, Vol. 57).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  1 Citation (Scopus)

  32 Downloads (Pure)
• 2015

  An optimal algorithm for the separating common tangents of two polygons

  Abrahamsen, M., 2015, In: Leibniz International Proceedings in Informatics. 34, p. 198-208 11 p.

  Research output: Contribution to journal › Conference article › Research › peer-review

  Open Access

  File
  3 Citations (Scopus)

  123 Downloads (Pure)

• Spiral toolpaths for high-speed machining of 2d pockets with or without islands

  Abrahamsen, M., 2015, Proceedings of the ASME 2015 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference IDETC/CIE 2015. American Society of Mechanical Engineers, Vol. 2B. 10 p. DETC2015-46255

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  File
• 2013

  An optimal algorithm computing edge-to-edge visibility in a simple polygon

  Abrahamsen, M., 2013, Proceedings of the 25th Canadian Conference on Computational Geometry: CCCG 2013. p. 157-162 6 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  File
  5 Citations (Scopus)