Source author record

Max Willert

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

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Routing in Unit Disk Graphs without Dynamic Headers

Let $V\subset\mathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$ . We develop a compact routing scheme for $DG(V)$ . The routing scheme preprocesses $DG(V)$ by assigning a label $l(v)$ to every site $v$ in $V$ . After that, for any two sites $s$ and $t$ , the scheme must be able to route a packet from $s$ to $t$ as follows: given the label of a current vertex $r$ (initially, $r=s$ ) and the label of the target vertex $t$ , the scheme determines a neighbor $r'$ of $r$ . Then, the packet is forwarded to $r'$ , and the process continues until the packet reaches its desired target $t$ . The resulting path between the source $s$ and the target $t$ is called the routing path of $s$ and $t$ . The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in $DG(V)$ , between any two sites $s, t \in V$ . We show that for any given $\varepsilon>0$ , we can construct a routing scheme for $DG(V)$ with diameter $D$ that achieves stretch $1+\varepsilon$ and label size $O(\log D\log^3n/\log\log n)$ (the constant in the $O$ -Notation depends on $\varepsilon$ ). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.

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.

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.