17 citations · 38 across the 17 of their papers we have counts for
13 papers · 1 filter
Guarding Polyominoes Under -Hop Visibility
Omrit Filtser, Erik Krohn, Bengt J. Nilsson +2
We study the Art Gallery Problem under -hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest p…
Opposing Half Guards
Erik Krohn, Bengt J. Nilsson, Christiane Schmidt
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location…
-Transmitter Watchman Routes
Bengt J. Nilsson, Christiane Schmidt
We consider the watchman route problem for a -transmitter watchman: standing at point in a polygon , the watchman can see if intersects 's bou…
Rectangular Spiral Galaxies are Still Hard
Erik D. Demaine, Maarten Löffler, Christiane Schmidt
Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers, the goal is to partition the grid into polyominoes such that ea…
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
Folding Polyominoes into (Poly)Cubes
Oswin Aichholzer, Michael Biro, Erik D. Demaine +6
We study the problem of folding a polyomino into a polycube , allowing faces of to be covered multiple times. First, we define a variety of folding models according to w…
Computing Nonsimple Polygons of Minimum Perimeter
Sándor P. Fekete, Andreas Haas, Michael Hemmer +8
We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertic…
The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS
Stephan Friedrichs, Michael Hemmer, James King +1
In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an -monotone chain of line segments in (the terrain ) and ask for the minimum number…
Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
Sarah Cannon, Thomas G. Fai, Justin Iwerks +2
We consider a generalization of the classical Art Gallery Problem, where instead of a light source, the guards, called -transmitters, model a wireless device with a signal that…
Algorithms for Art Gallery Illumination
Maximilian Ernestus, Stephan Friedrichs, Michael Hemmer +4
The Art Gallery Problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a give…
A PTAS for the continuous 1.5D Terrain Guarding Problem
Stephan Friedrichs, Michael Hemmer, Christiane Schmidt
In the continuous 1.5-dimensional terrain guarding problem we are given an -monotone chain (the \emph{terrain} ) and ask for the minimum number of point guards (located anywh…
Facets for Art Gallery Problems
Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller +1
The Art Gallery Problem (AGP) asks for placing a minimum number of stationary guards in a polygonal region P, such that all points in P are guarded. The problem is known to be NP-h…
Polygon Exploration with Time-Discrete Vision
Sandor P. Fekete, Christiane Schmidt
With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained i…