Выпуклая оболочка всех коллинеарных точек?

Это довольно тривиально, но все же я хотел знать, что было бы выпуклой оболочкой, если точки характеризуются линией x = y, т.е. все точки коллинеарны. Это был бы тот же случай, что и 2 точки, то есть отрезок, соединяющий все точки

0

Решение

Традиционно выпуклая оболочка набора точек вычисляется и выводится как выпуклая оболочка вершин (поскольку она такая же, как выпуклая оболочка исходного набора точек, но это меньшее и не избыточное описание). Таким образом, традиционно для вычисления выпуклой оболочки вы вычисляете вершины выпуклой оболочки и затем говорите, что все готово. Если все ваши точки лежат на прямой, то есть только две вершины: две крайние конечные точки вдоль линии. Таким образом, традиционно вы представляете выпуклую оболочку, говоря, что это выпуклая оболочка этих двух крайних точек (двух вершин), которая является отрезком, соединяющим две вершины по определению выпуклой оболочки.

2

Другие решения

От википедия, Выпуклая оболочка — это «самое маленькое выпуклое множество, содержащее X». Если это выпуклое множество является многоугольником, оно может быть представлено точками в его вершинах. Но это не очки.

Итак, что вы должны вывести, зависит от того, как задача просит вас представить выпуклую оболочку. Обычно вам нужно вывести только две самые дальние точки, но некоторые проблемы могут принимать коллинеарные точки в ответе.

В качестве упражнения подумайте, что выпуклая оболочка не может быть многоугольником:

выпуклый корпус

1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector