Алгоритмы и структуры данных

Выпуклая оболочка с использованием алгоритма «разделяй и властвуй»

Алгоритм:
1. если в наборе всего 3 или меньше точек, вычислите и верните их выпуклую оболочку напрямую.
2. Разделить: найти точку с наименьшей координатой X (а в случае ничьей — наименьшую координату Y) и точку с наибольшей координатой X (а в случае ничьей — наибольшую координату Y). . Эти две точки вместе с линией, соединяющей их, делят набор точек на верхнее и нижнее подмножество.
3. Рекурсия: рекурсивно найти выпуклые оболочки верхнего и нижнего подмножеств. Эти две выпуклые оболочки представляют собой части выпуклой оболочки выше и ниже разделительной линии.
4. Слияние: объедините верхнюю и нижнюю выпуклые оболочки, чтобы получить окончательную выпуклую оболочку.

Сложность: O(n*log n)

www.tgoop.com/the_algorithms/4682

5.4K viewsJan 27, 2024 at 09:00

Выпуклая оболочка с использованием алгоритма «разделяй и властвуй»

Алгоритм:
1. если в наборе всего 3 или меньше точек, вычислите и верните их выпуклую оболочку напрямую.
2. Разделить: найти точку с наименьшей координатой X (а в случае ничьей — наименьшую координату Y) и точку с наибольшей координатой X (а в случае ничьей — наибольшую координату Y). . Эти две точки вместе с линией, соединяющей их, делят набор точек на верхнее и нижнее подмножество.
3. Рекурсия: рекурсивно найти выпуклые оболочки верхнего и нижнего подмножеств. Эти две выпуклые оболочки представляют собой части выпуклой оболочки выше и ниже разделительной линии.
4. Слияние: объедините верхнюю и нижнюю выпуклые оболочки, чтобы получить окончательную выпуклую оболочку.

Сложность: O(n*log n)

BY Алгоритмы и структуры данных