activity
20132018
most citedComplexity of the General Chromatic Art Gallery Problem

5 citations · 13 across the 8 of their papers we have counts for

collaborators
Showing cs.CGShow all

7 papers · 1 filter

cs.CG2018

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…

cs.CG2015

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…

cs.CG2014★ 4 cited

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…

cs.CG2014

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…

cs.CG2014★ 4 cited

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…

cs.CG2014★ 5 cited

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…

cs.CG2013

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…