5 Search Results for "van Mulken, Max"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.10
Robotic Arm Rotation: Standing up Is Harder Than You Think

Authors: Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study motion-planning problems for planar robotic arms that rotate around fixed centers while avoiding collisions. In the SM-RAMP model, each unit-length arm may rotate at most once; the question is whether all arms can be rotated to the vertical position. We resolve an open problem of Bousquet et al. [Bousquet et al., 2026] by proving that SM-RAMP is NP-complete, even in the horizontal-to-vertical setting. Our hardness proof uses a structural analysis of rotation-propagation chains and introduces a combinatorial abstraction of independent interest, the Lighthouse Propagation problem, which we show is itself NP-complete. We then consider the multi-move variant MM-RAMP, where each arm may rotate multiple times among a fixed set of allowed angles (or orientations). We prove that MM-RAMP is PSPACE-complete even when each arm has only a few allowed angles, in sharp contrast with the single-move case. Finally, we give two fixed-parameter tractable algorithms: for MAX-SM-RAMP parameterized by the number k of arms to be made vertical, and for 2A-MM-RAMP (restricted to horizontal and vertical) parameterized by the number 𝓁 of allowed rotations.
Cite as

Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura, and Agnes Totschnig. Robotic Arm Rotation: Standing up Is Harder Than You Think. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.SWAT.2026.10,
  author =	{Bousquet, Nicolas and Connor, Frank and El Sabeh, Remy and Langevin, Louis-Roy and Mouawad, Amer E. and Nishimura, Naomi and Totschnig, Agnes},
  title =	{{Robotic Arm Rotation: Standing up Is Harder Than You Think}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.10},
  URN =		{urn:nbn:de:0030-drops-260467},
  doi =		{10.4230/LIPIcs.SWAT.2026.10},
  annote =	{Keywords: search, optimization, robotics, robotic arms, parameterized complexity, computational geometry, combinatorial reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.67
Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.
Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.26
Capturing the Shape of a Point Set with a Line Segment

Authors: Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group’s shape carries meaning as well. In this paper, we represent a group’s shape using a simple geometric object, a line segment. Specifically, given a radius r, we say a line segment is representative of a point set P of n points if it is within distance r of each point p ∈ P. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius r using the shortest line segment. We describe an algorithm to find the shortest representative segment in O(n log h + h log³h) time, where h is the size of the convex hull of P. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in P move.
Cite as

Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms. Capturing the Shape of a Point Set with a Line Segment. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanbeusekom_et_al:LIPIcs.MFCS.2024.26,
  author =	{van Beusekom, Nathan and van Kreveld, Marc and van Mulken, Max and Roeloffzen, Marcel and Speckmann, Bettina and Wulms, Jules},
  title =	{{Capturing the Shape of a Point Set with a Line Segment}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.26},
  URN =		{urn:nbn:de:0030-drops-205820},
  doi =		{10.4230/LIPIcs.MFCS.2024.26},
  annote =	{Keywords: Shape descriptor, Stabbing, Rotating calipers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.25
Dots & Boxes Is PSPACE-Complete

Authors: Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, and Max van Mulken

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Child’s Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.
Cite as

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, and Max van Mulken. Dots & Boxes Is PSPACE-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.MFCS.2021.25,
  author =	{Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max},
  title =	{{Dots \& Boxes Is PSPACE-Complete}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.25},
  URN =		{urn:nbn:de:0030-drops-144657},
  doi =		{10.4230/LIPIcs.MFCS.2021.25},
  annote =	{Keywords: Dots \& Boxes, PSPACE-complete, combinatorial game}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.79
Dots & Polygons (Media Exposition)

Authors: Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We present a new game, Dots & Polygons, played on a planar point set. We prove that its NP-hard and discuss strategies for the case when the point set is in convex position.
Cite as

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & Polygons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 79:1-79:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2020.79,
  author =	{Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max and Rensen, Jolan and van Schooten, Leo},
  title =	{{Dots \& Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{79:1--79:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.79},
  URN =		{urn:nbn:de:0030-drops-122371},
  doi =		{10.4230/LIPIcs.SoCG.2020.79},
  annote =	{Keywords: Dots \& Boxes, NP-hard, game, cycle packing}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2024
  • 1 2021
  • 1 2020

  • Refine by Author
  • 3 van Mulken, Max
  • 2 Buchin, Kevin
  • 2 Hagedoorn, Mart
  • 2 Kostitsyna, Irina
  • 1 Bousquet, Nicolas
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 2 Theory of computation → Complexity classes
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 Dots & Boxes
  • 1 Biclique covers
  • 1 NP-hard
  • 1 PSPACE-complete
  • 1 Rotating calipers
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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