Before revision:  The best optimal algorithm, due to Gudmundsson, van Kreveld, and Staals (2013), finds an axis-parallel square hotspot with fixed side length in O(n^2).
After revision:  The fastest optimal algorithm, due to Gudmundsson, van Kreveld, and Staals (2013), finds an axis-parallel square hotspot with fixed side length in O(n^2).