Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes

Manuel Cáceres, Sándor Kisfaludi-Bak, Saeed Odak

The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times $n^{O(1/{\epsilon }^{d-1})}$ for several $d$-dimensional geometric prob…