Кажется, что существует алгоритм в O(n.log(m)), см. в этой статье и в этом вопросе .
Моя оптимизация, которую вы можете попробовать: (не тестировалась)
Если ваши полигоны в большинстве случаев достаточно далеко друг от друга, вы можете построить два выпуклых корпуса и вернуться к самой простой задаче - найти расстояние Хаусдорфа между двумя выпуклыми полигонами (решение в O(n+m)). Если расстояние равно 0 , вам придется вернуться к случаю O(m.log(n)), но оно того стоит, если вы большую часть времени находитесь в случае "выпуклой оболочки" с положительным расстоянием.
Постскриптум . Я только что понял, что для того, чтобы постулат сработал, вам также необходимо проверить, что ближайшие элементы выпуклых оболочек принадлежат исходному вогнутому многоугольнику . Если нет, то легко найти контрпример (представьте многоугольник в форме буквы C с еще одним раундом рядом: CO).
Обновленный постулат будет таким: Расстояние Хаусдорфа d между двумя вогнутыми многоугольниками - это расстояние Хаусдорфа между их выпуклыми оболочками, если d > 0, и оба ближайших элемента являются частью оригинальные полигоны.
Доказательство этого оставлено читателю в качестве упражнения.