Возможно, вам следует проверить ( предупреждение в формате PDF! Также обратите внимание, что по какой-то причине порядок страниц меняется на обратный ) " Оптимальные алгоритмы для вычисления минимального расстояния между двумя конечными плоскими наборами "Туссеном и Бхаттачарьей:
В этой статье показано, что минимальное расстояние между двумя конечными плоскими множествами, если [ sic ] n точек может быть вычислено в O( n log n ) время работы в худшем случае, и это оптимально с точностью до постоянного коэффициента.Кроме того, когда множества образуют выпуклый многоугольник, эту сложность можно уменьшить до O ( n ).
Если два многоугольника пересекают выпуклые, возможно, вам также следует проверить( Предупреждение в формате PDF! Опять порядок страниц перевернут ) " Оптимальный алгоритм вычисления минимального расстояния между вершинами между двумя пересекающимися выпуклыми многоугольниками " по Туссену:
Let P = { p 1 , p 2 , ..., p m } и Q = { q 1 , q 2 , ..., q n } два пересекающихся многоугольника, вершины которых задаются своими декартовыми координатами по порядку.Представлен оптимальный алгоритм O ( m + n ) для вычисления минимального евклидова расстояния между вершинами p i in P и вершина q j in Q .