Geometric Burning Under $L_1$ and $L_{\infty }$ Metrics, and Beyond

Abstract

Burning is a discrete-time model for propagation in which a new fire starts in each round, while each existing fire expands by one unit of distance along the underlying metric. In geometric burning, the input is a finite point set, and the goal is to burn all points in as few rounds as possible. Equivalently, burning a point set in $k$ rounds corresponds to covering it with metric balls of distinct radii in $\{0,1,\dots ,k-1\}$; the objective is to minimize $k$. Previous work has studied the problem mainly under the Euclidean metric. In this paper, we study geometric burning under the $L_1$ and $L_{\infty }$ metrics. The problem remains NP-hard in both settings. The $L_1$ and $L_{\infty }$ metrics provide additional geometric structure, which allows us to obtain improved approximation guarantees, especially for anywhere burning. We first present a simple $(2+\epsilon )$-approximation for both anywhere burning and point burning. We then improve the anywhere burning approximation to $7/4+\epsilon =1.75+\epsilon$, and give a $(3151/1620+\epsilon )$-approximation for point burning, where $3151/1620<1.9451$. We also extend the anywhere burning result under $L_{\infty }$ to every fixed dimension $d\ge 3$ to achieve a $\left(2-\frac{1}{2^{d+1}}+\epsilon \right)$-approximation. Finally, using standard comparisons between planar $L_p$ distances, we transfer our $L_1$ and $L_{\infty }$ algorithms, together with known Euclidean burning algorithms, to obtain approximation guarantees for every fixed $1\le p\le \infty$.

arXiv comment13 pages, 4 figures. Accepted at the Workshop on Approximation and Online Algorithms (WAOA 2026)