28 citations · 92 across the 12 of their papers we have counts for
14 papers
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…
A Parallel Distributed Strategy for Arraying a Scattered Robot Swarm
Dominik Krupke, Michael Hemmer, James McLurkin +2
We consider the problem of organizing a scattered group of robots in two-dimensional space, with geometric maximum distance between robots. The communication graph of the s…
Distributed Cohesive Control for Robot Swarms: Maintaining Good Connectivity in the Presence of Exterior Forces
Dominik Krupke, Maximilian Ernestus, Michael Hemmer +1
We present a number of powerful local mechanisms for maintaining a dynamic swarm of robots with limited capabilities and information, in the presence of external forces and permane…
Exact Minkowski Sums of Polygons With Holes
Alon Baram, Efi Fogel, Michael Hemmer +2
We present an efficient algorithm that computes the Minkowski sum of two polygons, which may have holes. The new algorithm is based on the convolution approach. Its efficiency stem…
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…
Improved Implementation of Point Location in General Two-Dimensional Subdivisions
Michael Hemmer, Michal Kleinbort, Dan Halperin
We present a major revamp of the point-location data structure for general two-dimensional subdivisions via randomized incremental construction, implemented in CGAL, the Computatio…
On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages
Oren Salzman, Michael Hemmer, Dan Halperin
We extend our study of Motion Planning via Manifold Samples (MMS), a general algorithmic framework that combines geometric methods for the exact and complete analysis of low-dimens…
Motion Planning via Manifold Samples
Oren Salzman, Michael Hemmer, Barak Raveh +1
We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of low-dimensional conf…