Dear all,
There will be a noon seminar this Thursday, 3 April, given by Vahideh Keikha. Please find the talk details below.
Best regards, Misha Tyomkyn.
-------------------------
Guarding a 1.5D Terrain with Multiple Imprecise Viewpoints Vahideh Keikha Czech Academy of Sciences April 3, 2025, 12:20 in S6
Abstract Given an $n$-vertex 1.5D terrain $\T$ and a set of $m$ edges of $\T$, we study the problem of placing one viewpoint on each edge so that the total length of the visible portions of the terrain is maximized. We present an $O(n+m \log m )$ time $\frac{1}{2}$-approximation algorithm for the general problem, and polynomial-time algorithms for the cases $m=1$ and $m=2$. Additionally, we show that the problem of computing a point on $\T$ maximizing the visible portion of $\T$ can be solved in $O(n^3)$ time.
-------------------------