A Sub-quadratic Time Algorithm for Computing the Beacon Kernel of Simple Polygons

In 2011, Biro et al. [4] initiated the concept of beacon attraction trajectory motivated by routing messages in sensor network systems. Let P be a polygonal region such that there is a point particle at each point in P. When we activate a beacon at a point \(b\in P\) , each particle in P greedily moves toward b. For a point \(p\in P\) , if the particle at p reaches b, we say b attracts p. We call a point \(b\in P\) a beacon kernel point of P if a beacon at b attracts all points in P. The beacon kernel of P is defined as the set of all beacon kernel points of P. In 2013 [3] Biro presented a naive quadratic time algorithm to compute the beacon kernel of polygonal domains and showed that this bound is tight. But, obtaining a sub-quadratic time algorithm for computing the beacon kernel of simple polygons remained open. In this paper, we answer to this open problem by presenting an \(O(n^{1.5}\log ^2 n)\) time algorithm for computing the beacon kernel of simple polygons.