28 citations · 92 across the 12 of their papers we have counts for
6 papers · 1 filter
Optimal randomized incremental construction for guaranteed logarithmic planar point location
Michael Hemmer, Michal Kleinbort, Dan Halperin
Given a planar map of segments in which we wish to efficiently locate points, we present the first randomized incremental construction of the well-known trapezoidal-map search-…
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…
Efficient Computation of Visibility Polygons
Francisc Bungiu, Michael Hemmer, John Hershberger +2
Determining visibility in planar polygons and arrangements is an important subroutine for many algorithms in computational geometry. In this paper, we report on new implementations…
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…