A reminder: this is today.
---------------------------
On 2025-03-31 10:04, Mykhaylo Tyomkyn wrote:
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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz