Я хотел бы знать различные алгоритмы, чтобы найти самый большой квадрат в двухмерной карте, усеянной препятствиями.

Пример, гдеo будут препятствия

...........................
....o......................
............o..............
...........................
....o......................
...............o...........
...........................
......o..............o.....
..o.......o................

Самый большой квадрат будет (если мы выберем первый):

.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxxo..............
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxx...o...........
.....xxxxxxx...............
......o..............o.....
..o.......o................

Какой будет самый быстрый алгоритм, чтобы найти его? Тот, с наименьшей сложностью?

РЕДАКТИРОВАТЬ: Я знаю, что люди интересуются алгоритмом, объясненным в принятом ответе, поэтому я сделал документ, который объясняет это немного больше, вы можете найти его здесь:

https://docs.google.com/document/d/19pHCD433tYsvAor0WObxa2qusAjKdx96kaf3z5I8XT8/edit?usp=sharing