Я ищу алгоритм, чтобы найти самый длинный аккорд ( "диаметр" ) замкнутой полилинии. К сожалению, полилиния не должна быть выпуклой, но аккорд должен лежать целиком внутри кривой. Вот пример:
Решение, которое я ищу, - это разбитый красный сегмент.
Можете ли вы предложить эффективный алгоритм для этого? Самое лучшее, что нам удалось достичь до сих пор, - это алгоритм N², который пробует все пары вершин, но даже это кажется неправильным, поскольку хорда не обязательно проходит через две вершины (или делает это?).
Меня также интересует связанная с этим проблема, когда мы ищем самый большой сегмент, соединяющий две вершины (или самую длинную часть этого сегмента, которая лежит внутри кривой, если сегмент не полностью вписан). В этом случае алгоритм N² работает, но медленен для большого количества точек.
