Speaker: Oren Salzman (TAU) Title: An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles Abstract: In this talk I will study a path-planning problem amid a set~$O$ of obstacles in~$\R^2$, in which we wish to compute a short path between two points while also maintaining a high clearance from~$O$; the clearance of a point is its distance from a nearest obstacle in~$O$. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. I will present the first polynomial-time approximation scheme for this problem. Let~$n$ be the total number of obstacle vertices and let~$\eps \in (0,1]$. The algorithm computes in time $O(\frac{n^2}{\eps^2} \log \frac{n}{\eps})$ a path of total cost at most~$(1+\eps)$ times the cost of the optimal path. This is joint work with Pankaj Agarwal and Kyle Fox that will be presented at SODA16.