2-Approximation for the Min. $k$-Enclosing Geodesic Disc in a Simple Polygon

Anthony D'Angelo

Carleton University

I will present the algorithm I am currently working on that uses random sampling and a combination of polygon decomposition and $k$-levels to get a 2-approximation algorithm for the min enclosing geodesic disc of $k$ points in simple polygons. The polygon has $m$ vertices total, $r$ reflex vertices, and the set of points $S$ that our $k$ points is to be chosen from has size $n$. After $O(m+(n + r)\log(r))$ preprocessing, the runtime of the current approach is $O((n^{11/7}\log^2(n)+nr)\log(r))$.