17 citations · 38 across the 17 of their papers we have counts for
19 papers
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…
On Minimal Sets to Destroy the -Core in Random Networks
Christian Schmidt, Henry D. Pfister, Lenka Zdeborová
We study the problem of finding the smallest set of nodes in a network whose removal results in an empty -core; where the -core is the sub-network obtained after the iterativ…
Dense Limit of the Dawid-Skene Model for Crowdsourcing and Regions of Sub-optimality of Message Passing Algorithms
Christian Schmidt, Lenka Zdeborová
Crowdsourcing is a strategy to categorize data through the contribution of many individuals. A wide range of theoretical and algorithmic contributions are based on the model of Daw…
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…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Circular Coloring of Random Graphs: Statistical Physics Investigation
Christian Schmidt, Nils-Eric Guenther, Lenka Zdeborová
Circular coloring is a constraints satisfaction problem where colors are assigned to nodes in a graph in such a way that every pair of connected nodes has two consecutive colors (t…
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…
Minimum Covering with Travel Cost
Sandor P. Fekete, Joseph S. B. Mitchell, Christiane Schmidt
Given a polygon and a visibility range, the Myopic Watchman Problem with Discrete Vision (MWPDV) asks for a closed path P and a set of scan points S, such that (i) every point of t…
Empowered by Wireless Communication: Self-Organizing Traffic Collectives
Sándor P. Fekete, Christiane Schmidt, Axel Wegener +2
In recent years, tremendous progress has been made in understanding the dynamics of vehicle traffic flow and traffic congestion by interpreting traffic as a multi-particle system.…
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…