Места, где порядок точек вдоль простого многоугольника, проходящего через них, полезен

10

Мы знаем, что нахождение выпуклой оболочки из n точек на плоскости имеет нижнюю границу Ω(nlogn) по времени ее работы. Однако если точки заданы в том порядке, в котором они расположены вдоль некоторого простого многоугольника, в котором эти точки являются его вершинами, то их выпуклая оболочка может быть найдена за линейное время.

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

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

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

Винаяк Патхак
источник

Ответы:

10

nn!(n1)!/22Θ(nlogn)

2Θ(n)<30n<23n6

Выпуклая оболочка простых многоугольников была одной из моих любимых вещей с тех пор, как я использовала ее для поиска и / или формул для многоугольников в SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472

Джек
источник