Source author record

Klaus Kriegel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Robotics

Catalog footprint

Research overview

2works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Almost Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Galleries

We address recently proposed chromatic versions of the classic Art Gallery Problem. Assume a simple polygon $P$ is guarded by a finite set of point guards and each guard is assigned one of $t$ colors. Such a chromatic guarding is said to be conflict-free if each point $p\in P$ sees at least one guard with a unique color among all guards visible from $p$ . The goal is to establish bounds on the function $χ_{cf}(n)$ of the number of colors sufficient to guarantee the existence of a conflict-free chromatic guarding for any $n$ -vertex polygon. Bärtschi and Suri showed $χ_{cf}(n)\in O(\log n)$ (Algorithmica, 2014) for simple orthogonal polygons and the same bound applies to general simple polygons (Bärtschi et al., SoCG 2014). In this paper, we assume the r-visibility model instead of standard line visibility. Points $p$ and $q$ in an orthogonal polygon are r-visible to each other if the rectangle spanned by the points is contained in $P$ . For this model we show $χ_{cf}(n)\in O(\log\log n)$ and $χ_{cf}(n)\in Ω(\log\log n /\log\log\log n)$ . Most interestingly, we can show that the lower bound proof extends to guards with line visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau. This is the first non-trivial lower bound for this problem setting.Furthermore, for the strong chromatic version of the problem, where all guards r-visible from a point must have distinct colors, we prove a $Θ(\log n)$ -bound. Our results can be interpreted as coloring results for special geometric hypergraphs.

preprint2012arXiv

Online Exploration of Polygons with Holes

We study online strategies for autonomous mobile robots with vision to explore unknown polygons with at most h holes. Our main contribution is an (h+c_0)!-competitive strategy for such polygons under the assumption that each hole is marked with a special color, where c_0 is a universal constant. The strategy is based on a new hybrid approach. Furthermore, we give a new lower bound construction for small h.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.