5 citations · 13 across the 8 of their papers we have counts for
9 papers
Altitude Terrain Guarding and Guarding Uni-Monotone Polygons
Ovidiu Daescu, Stephan Friedrichs, Hemant Malik +2
We present an optimal, linear-time algorithm for the following version of terrain guarding: given a 1.5D terrain and a horizontal line, place the minimum number of guards on the li…
Metastability-Containing Circuits
Stephan Friedrichs, Matthias Függer, Christoph Lenzen
In digital circuits, metastability can cause deteriorated signals that neither are logical 0 or logical 1, breaking the abstraction of Boolean logic. Unfortunately, any way of read…
Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Stephan Friedrichs, Christoph Lenzen
A \emph{metric tree embedding} of expected \emph{stretch~} maps a weighted -node graph to a weighted tree with s…
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…
Engineering Art Galleries
Pedro J. de Rezende, Cid C. de Souza, Stephan Friedrichs +3
The Art Gallery Problem is one of the most well-known problems in Computational Geometry, with a rich history in the study of algorithms, complexity, and variants. Recently there h…
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…
Complexity of the General Chromatic Art Gallery Problem
Sándor P. Fekete, Stephan Friedrichs, Michael Hemmer
In the original Art Gallery Problem (AGP), one seeks the minimum number of guards required to cover a polygon . We consider the Chromatic AGP (CAGP), where the guards are colore…
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…