10 Search Results for "Stade, Jack"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.14
Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

Authors: Jaehoon Chung

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

Abstract
We study a variant of a polygon partition problem, introduced by Chung, Iwama, Liao, and Ahn [ISAAC'25]. Given orthogonal unit vectors 𝐮,𝐯 ∈ ℝ² and a polygon P with n vertices, we partition P into connected pieces by cuts parallel to 𝐯 such that each resulting subpolygon has width at most one in direction 𝐮. We consider the value version, which asks for the minimum number of strips, and the reporting version, which outputs a compact encoding of the cuts in an optimal strip partition. We give efficient algorithms and lower bounds for both versions on three classes of polygons of increasing generality: convex, simple, and self-overlapping. For convex polygons, we solve the value version in O(log n) time and the reporting version in O(h log (1 + n/h)) time, where h is the width of P in direction 𝐮. We prove matching lower bounds in the decision-tree model, showing that the reporting algorithm is input-sensitive optimal with respect to h. For simple polygons, we present O(n log n)-time, O(n)-space algorithms for both versions and prove an Ω(n) lower bound. For self-overlapping polygons, we extend the approach for simple polygons to obtain O(n log n)-time, O(n)-space algorithms for both versions, and we prove a matching Ω(n log n) lower bound in the algebraic computation-tree model via a reduction from the δ-closeness problem. Our approach relies on a lattice-theoretic formulation of the problem. We represent strip partitions as antichains of intervals in the Clarke-Cormack-Burkowski lattice, originally developed for minimal-interval semantics in information retrieval. Within this lattice framework, we design a dynamic programming algorithm that uses the lattice operations of meet and join. To the best of our knowledge, this is the first geometric application of the Clarke-Cormack-Burkowski lattice.
Cite as

Jaehoon Chung. Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chung:LIPIcs.SWAT.2026.14,
  author =	{Chung, Jaehoon},
  title =	{{Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-260506},
  doi =		{10.4230/LIPIcs.SWAT.2026.14},
  annote =	{Keywords: Polygon partitioning, Strip partition, Lattice, Self-overlapping curves}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.1
Covering and Partitioning Complex Objects with Small Pieces

Authors: Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study the problems of covering or partitioning a polygon P (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contained in an axis-aligned unit square. For covering, we seek to write P as a union of small pieces, and in partitioning, we furthermore require the pieces to be pairwise interior-disjoint. We show that these problems are in fact equivalent: Optimum covers and partitions have the same number of pieces. For covering, a natural local search algorithm repeatedly attempts to replace k pieces from a candidate cover with k-1 pieces. In two dimensions and for sufficiently large k, we show that when no such swap is possible, the cover is a 1+ O(1/√k) approximation, hence obtaining the first PTAS for the problem. Prior to our work, the only known algorithm was a 13-approximation that only works for polygons without holes [Abrahamsen and Rasmussen, SODA 2025]. In contrast, in the three dimensional version of the problem, for a polyhedron P of complexity n, we show that it is NP-hard to approximate an optimal cover or partition to within a factor that is logarithmic in n, even if P is simple, i.e., has genus 0 and no holes.
Cite as

Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade. Covering and Partitioning Complex Objects with Small Pieces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2026.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Browne, Reilly and Goswami, Mayank and Kasthurirangan, Prahlad Narasimhan and Kleist, Linda and Mitchell, Joseph S. B. and Polishchuk, Valentin and Stade, Jack},
  title =	{{Covering and Partitioning Complex Objects with Small Pieces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.1},
  URN =		{urn:nbn:de:0030-drops-258077},
  doi =		{10.4230/LIPIcs.SoCG.2026.1},
  annote =	{Keywords: Covering, partitioning, polygon, small piece, PTAS}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.43
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs

Authors: Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Solovey et al. (RSS'15) provide a near-optimal solution assuming that start/target positions must have pairwise distance at least 4, and at least √5≈2.236 from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is 2 2/3 and the obstacles-separation is 1 2/3, or (ii) the robots-separation is ≈3.291 and the obstacles-separation ≈1.354. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only 2, and the obstacles-separation is 3. Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 may be necessary for a solution to exist.
Cite as

Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein. Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{farhana_et_al:LIPIcs.SoCG.2026.43,
  author =	{Farhana, Tsuri and Filtser, Omrit and Goldshtein, Shalev},
  title =	{{Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.43},
  URN =		{urn:nbn:de:0030-drops-258495},
  doi =		{10.4230/LIPIcs.SoCG.2026.43},
  annote =	{Keywords: multi-robot motion planning}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.32
Tetris Is Hard with Just One Piece Type

Authors: MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della Hendrickson, and Jeffery Li

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type P except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of P pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a 7k-bag randomizer for any positive integer k ≥ 1. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with 1 × k pieces (for any fixed k), provided the top k-1 rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.
Cite as

MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della Hendrickson, and Jeffery Li. Tetris Is Hard with Just One Piece Type. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2026.32,
  author =	{MIT Hardness Group and Brunner, Josh and Demaine, Erik D. and Hendrickson, Della and Li, Jeffery},
  title =	{{Tetris Is Hard with Just One Piece Type}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.32},
  URN =		{urn:nbn:de:0030-drops-257515},
  doi =		{10.4230/LIPIcs.FUN.2026.32},
  annote =	{Keywords: complexity, hardness, video games, counting}
}
Document
DOI: 10.4230/OASIcs.PARMA-DITAM.2026.5
LAMINA: An MLIR-Based Translation Library for Heterogeneous Quantum-Classical Compilation

Authors: Marco De Pascale, Mario Hernández Vera, Jorge Echavarria, Muhammad Nufail Farooqi, Martin Schulz, and Laura Schulz

Published in: OASIcs, Volume 141, 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)

Abstract
Quantum computing is increasingly integrated into High-Performance Computing (HPC) environments, where quantum processors act as specialized accelerators within hybrid workflows. The Munich Quantum Software Stack (MQSS) - a unified compilation and runtime framework for hybrid quantum–classical computing - provides the foundation for this integration. However, the growing heterogeneity of applications demands more flexible compilation tools. This work introduces an MultiLevel Intermediate Representation (MLIR)-based translation library that extends MQSS by enabling the conversion of CUDA-Quantum (CUDA-Q) (quake) dialects into machine learning–oriented MLIR representations compatible with modern compiler ecosystems. Leveraging MLIR’s dialect-driven design, the library enables hardware-agnostic transformations, device-specific optimizations, and seamless integration with MQSS components. The proposed approach bridges quantum compilation and contemporary machine learning frameworks, facilitating GPU-accelerated circuit simulation, hybrid quantum–classical workflows, and heterogeneous execution, thereby advancing a unified compiler infrastructure for quantum computing.
Cite as

Marco De Pascale, Mario Hernández Vera, Jorge Echavarria, Muhammad Nufail Farooqi, Martin Schulz, and Laura Schulz. LAMINA: An MLIR-Based Translation Library for Heterogeneous Quantum-Classical Compilation. In 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026). Open Access Series in Informatics (OASIcs), Volume 141, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{depascale_et_al:OASIcs.PARMA-DITAM.2026.5,
  author =	{De Pascale, Marco and Hern\'{a}ndez Vera, Mario and Echavarria, Jorge and Nufail Farooqi, Muhammad and Schulz, Martin and Schulz, Laura},
  title =	{{LAMINA: An MLIR-Based Translation Library for Heterogeneous Quantum-Classical Compilation}},
  booktitle =	{17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)},
  pages =	{5:1--5:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-416-1},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{141},
  editor =	{Baroffio, Davide and Busia, Paola and Denisov, Lev and Shukla, Nitin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2026.5},
  URN =		{urn:nbn:de:0030-drops-256720},
  doi =		{10.4230/OASIcs.PARMA-DITAM.2026.5},
  annote =	{Keywords: HPCQC, MLIR, Quantum Computing, Heterogeneous Computing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.22
Minimum Partition of Polygons Under Width and Cut Constraints

Authors: Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in predetermined directions such that each resulting subpolygon satisfies a given width constraint. A polygon satisfies the unit-width constraint for a set of unit vectors if the length of the orthogonal projection of the polygon on a line parallel to a vector in the set is at most one. We analyze structural properties of the minimum partition numbers, focusing on monotonicity under polygon containment. We show that the minimum partition number of a simple polygon is at least that of any subpolygon, provided that the subpolygon satisfies a certain orientation-wise convexity with respect to the polygon. As a consequence, we prove a partition analogue of the Bang’s conjecture about coverings of convex regions in the plane: for any partition of a convex body in the plane, the sum of relative widths of all parts is at least one. For any convex polygon, there exists a direction along which an optimal partition is achieved by parallel cuts. Given such a direction, an optimal partition can be computed in linear time.
Cite as

Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn. Minimum Partition of Polygons Under Width and Cut Constraints. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ISAAC.2025.22,
  author =	{Chung, Jaehoon and Iwama, Kazuo and Liao, Chung-Shou and Ahn, Hee-Kap},
  title =	{{Minimum Partition of Polygons Under Width and Cut Constraints}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.22},
  URN =		{urn:nbn:de:0030-drops-249302},
  doi =		{10.4230/LIPIcs.ISAAC.2025.22},
  annote =	{Keywords: Polygon partitioning, Width constraints, Plank problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.20
Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Authors: Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.
Cite as

Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.20,
  author =	{Biniaz, Ahmad and Maheshwari, Anil and Merrild, Magnus Christian Ring and Mitchell, Joseph S. B. and Odak, Saeed and Polishchuk, Valentin and Robson, Eliot W. and Rysgaard, Casper Moldrup and Schou, Jens Kristian Refsgaard and Shermer, Thomas and Spalding-Jamieson, Jack and Svenning, Rolf and Zheng, Da Wei},
  title =	{{Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.20},
  URN =		{urn:nbn:de:0030-drops-231720},
  doi =		{10.4230/LIPIcs.SoCG.2025.20},
  annote =	{Keywords: Art Gallery Problem, Computational Geometry, Combinatorics, Discrete Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.74
The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard

Authors: Jack Stade

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is ∃ℝ-complete, meaning that it is equivalent under polynomial time reductions to deciding whether a system of polynomial equations has a real solution. The art gallery problem asks whether there is a configuration of guards that together can see every point inside of an art gallery modeled by a simple polygon. The original version of this problem (which we call the point-point variant) was shown to be ∃ℝ-hard [Abrahamsen, Adamaszek, and Miltzow, JACM 2021], but the complexity of the variant where guards only need to guard the walls of the art gallery was left as an open problem. We show that this variant is also ∃ℝ-hard. Our techniques can also be used to greatly simplify the proof of ∃ℝ-hardness of the point-point art gallery problem. The gadgets in previous work could only be constructed by using a computer to find complicated rational coordinates with specific algebraic properties. All of our gadgets can be constructed by hand and can be verified with simple geometric arguments.
Cite as

Jack Stade. The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 74:1-74:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{stade:LIPIcs.SoCG.2025.74,
  author =	{Stade, Jack},
  title =	{{The Point-Boundary Art Gallery Problem Is \exists\mathbb{R}-Hard}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{74:1--74:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.74},
  URN =		{urn:nbn:de:0030-drops-232269},
  doi =		{10.4230/LIPIcs.SoCG.2025.74},
  annote =	{Keywords: Art Gallery Problem, Complexity, ETR, Polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.1
Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings

Authors: Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, and Jack Stade

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the start configuration to the target configuration while avoiding collisions between the objects and staying within the polygon. Problems of this type have been considered since the early 80s by roboticists and computational geometers. In this paper, we study some of the simplest possible variants where the objects are labeled or unlabeled unit squares or unit disks. In unlabeled reconfiguration, the objects are identical, so that any object is allowed to end at any of the targets positions. In the labeled variant, each object has a designated target position. The results for the labeled variants are direct consequences from our insights on the unlabeled versions. We show that it is PSPACE-hard to decide whether there exists a reconfiguration of (unlabeled/labeled) unit squares even in a simple polygon. Previously, it was only known to be PSPACE-hard in a polygon with holes for both the unlabeled and labeled version [Solovey and Halperin, Int. J. Robotics Res. 2016]. Our proof is based on a result of independent interest, namely that reconfiguration between two satisfying assignments of a formula of Monotone-Planar-3-Sat is also PSPACE-complete. The reduction from reconfiguration of Monotone-Planar-3-Sat to reconfiguration of unit squares extends techniques recently developed to show NP-hardness of packing unit squares in a simple polygon [Abrahamsen and Stade, FOCS 2024]. We also show PSPACE-hardness of reconfiguration of (unlabeled/labeled) unit disks in a polygon with holes. Previously, it was known that unlabeled reconfiguration of disks of two different sizes was PSPACE-hard [Brocken, van der Heijden, Kostitsyna, Lo-Wong and Surtel, FUN 2021].
Cite as

Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, and Jack Stade. Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2025.1,
  author =	{Abrahamsen, Mikkel and Buchin, Kevin and Buchin, Maike and Kleist, Linda and L\"{o}ffler, Maarten and Schlipf, Lena and Schulz, Andr\'{e} and Stade, Jack},
  title =	{{Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.1},
  URN =		{urn:nbn:de:0030-drops-231539},
  doi =		{10.4230/LIPIcs.SoCG.2025.1},
  annote =	{Keywords: reconfiguration, unit square, unit disk, unlabeled, labeled, simple polygon, polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.58
Topological Universality of the Art Gallery Problem

Authors: Jack Stade and Jamie Tucker-Foltz

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

Abstract
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but holding only up to homotopy equivalence, rather than homeomorphism, and prior to this work, the existence of art galleries even for simple spaces such as the Möbius strip or the three-holed torus were unknown. Our construction relies on an elegant and versatile gadget to copy guard positions with minimal overhead. It is simpler than previous constructions, consisting of a single rectangular room with convex slits cut out from the edges. We show that both the orientable and non-orientable surfaces of genus n admit galleries with only O(n) vertices.
Cite as

Jack Stade and Jamie Tucker-Foltz. Topological Universality of the Art Gallery Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{stade_et_al:LIPIcs.SoCG.2023.58,
  author =	{Stade, Jack and Tucker-Foltz, Jamie},
  title =	{{Topological Universality of the Art Gallery Problem}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{58:1--58:13},
  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.58},
  URN =		{urn:nbn:de:0030-drops-179082},
  doi =		{10.4230/LIPIcs.SoCG.2023.58},
  annote =	{Keywords: Art gallery, Homeomorphism, Exists-R, ETR, Semi-algebraic sets, Universality}
}
  • Refine by Type
  • 10 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 4 2025
  • 1 2023

  • Refine by Author
  • 4 Stade, Jack
  • 2 Abrahamsen, Mikkel
  • 2 Chung, Jaehoon
  • 2 Kleist, Linda
  • 2 Mitchell, Joseph S. B.
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 7 Theory of computation → Computational geometry
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Computer systems organization → Quantum computing
  • 1 Software and its engineering → Just-in-time compilers
  • 1 Software and its engineering → Retargetable compilers
  • Show More...

  • Refine by Keyword
  • 2 Art Gallery Problem
  • 2 ETR
  • 2 Polygon partitioning
  • 2 polygon
  • 1 Art gallery
  • 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