The Polygon Burning Problem
share
Motivated by the k-center problem in location analysis, we consider the polygon burning (PB) problem: Given a polygonal domain P with h holes and n vertices, find a set S of k vertices of P that minimizes the maximum geodesic distance from any point in P to its nearest vertex in S. Alternatively, viewing each vertex in S as a site to start a fire, the goal is to select S such that fires burning simultaneously and uniformly from S, restricted to P, consume P entirely as quickly as possible. We prove that PB is NP-hard when k is arbitrary. We show that the discrete k-center of the vertices of P under the geodesic metric on P provides a 2-approximation for PB, resulting in an O(n^2 log n + hkn log n)-time 3-approximation algorithm for PB. Lastly, we define and characterize a new type of polygon, the sliceable polygon. A sliceable polygon is a convex polygon that contains no Voronoi vertex from the Voronoi diagram of its vertices. We give a dynamic programming algorithm to solve PB exactly on a sliceable polygon in O(kn^2) time.
READ FULL TEXT