Проверка, образует ли набор из n точек на плоскости выпуклый n-многоугольник за время o (nlogn)

Предположим, что вам дан набор из n точек на плоскости, и вы хотите проверить, образуют ли они выпуклый n-многоугольник, т. Е. Лежат ли все они на выпуклой оболочке. Мне было интересно, если кто-нибудь знает, как это сделать за время (nlogn), т. Е. Без вычисления CH.

cg.comp-geom Бабис Цуракакис
источник

Вы можете вычислить выпуклую оболочку за O (n log n) времени. Вы имеете в виду, если это возможно сделать за меньшее время, чем это?

Per Vognsen

да, я считаю, что должен быть какой-то линейный алгоритм времени для этой проблемы. но я не знаю как

Бабис Цуракакис

Он написал o (nlogn), а не O (nlogn), поэтому его вопрос правильный.

Шива Кинтали

Я использую маленькую нотацию, поэтому вопрос остается без изменений

Бабис Цуракакис

Это заставляет меня немного хмуриться, когда я вижу, как сортировка чисел (или эквивалентно выпуклых оболочек декартовых точек) определяется как занимающая Θ (n log n) времени без явного указания, какую модель вычислений вы используете. Сортировка сравнений занимает Θ (n log n) времени, но модель сравнения даже не позволяет вычислять оболочки вообще. Они оба все еще тратят time (n log n) времени на алгебраические деревья решений (как показывает принятый ответ), но быстрее в моделях вычислений, которые больше похожи на реальные компьютеры.

Дэвид Эппштейн

Ответы:

Это кажется маловероятным, по крайней мере, в моделях сравнения / алгебраического дерева. Определение первое:

Точка множество находится в выпуклом положении , если ни одна точка не может быть записана в виде выпуклой комбинации остальных точек . $P$ $P$ $P$

Теперь, чтобы решить, все ли числа из чисел различны, требуется время (это называется УНИКАЛЬНОСТЬЮ). Учитывая такой набор из чисел , сопоставьте их множеству точек Если повторного числа нет, то точки находятся в выпуклом положении. $n$ $\Omega(n \log n)$ $n$ $X$

P = {(x, x^{2}) | x \in X} .

$P = \{ (x, x^2) | x \in X\}.$

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

А именно, решить, находится ли набор точек в выпуклом положении, так же сложно, как и УНИКАЛЬНОСТЬ.

Сариэль Хар-Пелед
источник

X [i]

$X[i]$

(X [i], X [i]^{2} + i / n^{2})

$(X[i], X[i]^2+i/n^2)$

@Babis: сокращение Джеффа работает, когда повторяющиеся точки не допускаются. Точки, сгенерированные при уменьшении, являются уникальными, независимо от исходного массива.

Винаяк Патхак

Таким образом, мы получаем, что число углов выпуклой оболочки равно n тогда и только тогда, когда никакие две точки не имеют одинаковую x-координату. Большое спасибо, изначально я думал, что это должно быть проще, чем сортировка.

Бабис Цуракакис

Благодаря Vinayak, я не видел сокращение Джеффа, так как оно было опубликовано в то же время, когда я писал предыдущий комментарий, который я заменил выше

Babis Tsourakakis

Суреш, я не согласен с фразой "стандартная модель". Это именно то, что представляет собой Word RAM :) Это модель, которая наиболее близко соответствует реальному компьютеру и которую мы используем для анализа алгоритма в большинстве TCS. Геометрия признала исключение для использования реальной оперативной памяти, чтобы нам не приходилось сталкиваться с проблемами точности. Но это не «стандартная модель».

Михай

-1

$O(n log n)$

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

Получение внутренней точки зрения оставлено в качестве упражнения для читателя.

$O(n log n)$

BCS
источник

Вы, вероятно, неправильно прочитали его o (n log n) как O (n log n) так же, как я. Во всяком случае, алгоритм, который вы изложили, это упаковка подарков в зачаточном виде. Вам на самом деле не нужно использовать внутреннюю точку; Вы можете использовать точку на границе, например, точку с минимальной координатой х.

В Вогнсен

O (n l o g n)

$O(n log n)$

o ()

$o()$

Дело в том, что существует множество алгоритмов выпуклой оболочки, которые работают в O (n log n). Ваш алгоритм - это просто старая подарочная упаковка. Он просил что-то быстрее, например, линейное время. Смотрите другие ответы.

В Вогнсен

Что касается вашего редактирования, если вы посмотрите на принятый ответ выше вашего, вы увидите, что проблема эквивалентна уникальности элемента, который имеет нижнюю границу O (n log n).

Per Vognsen

@BCS: Боюсь, что у вас возникло недоразумение относительно ответа Сариэля Хар-Пеледа. Сокращение от уникальности до выпуклого позиционного тестирования, а не другого направления. То есть Сариэль (и Джефф) заявили, что если вам дан набор чисел и вы хотите проверить уникальность, вы можете преобразовать его в набор точек и использовать любой алгоритм для проверки выпуклых позиций.

Цуёси Ито