Before revision:  The fastest optimal algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) , finds an axis-parallel square hotspot of 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 of fixed side length in O(n^2).