Может какой-то известный алгоритм есть, и не надо велосипед выдумывать?
Может и есть, но я бы особо на это не рассчитывал. Напр Германия, Польша и Белоруссия - подписаны явно так чтобы перекрывалось минимум содержимого (названия столиц, городов и.т.п). Куча исключений - напр Малайзия, Индонезия. Я бы начал с банального bounding box и попытался бы построить "путь", по нему уже надпись
Да, красивая карта, с детства люблю рассматривать