Разделение предварительно обработанного многогранника и плоскости

У меня есть серьезные проблемы с пониманием одного шага в статье Добкина и Киркпатрика о разделении многогранников. Я пытаюсь понять эту версию: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

Он утверждает, что после того, как мы знаем лучшее разделение и , реализованное с помощью и , мы можем найти лучшее разделение и за шагов. Это делается следующим образом. Мы берем плоскость, параллельную через и разрезаем на две части. С одной стороны, ближайшая точка к - это а с другой стороны у нас есть «элементарный» многогранник, который мы можем проверить за раз. Моя проблема - как нам найти этот элементарный многогранник? Обратите внимание, что степень $P_{i}$ $S$ $r_i$ $s_i$ $P_{i-1}$ $S$ $O(1)$ $S$ $r_i$ $P_{i-1}$ $S$ $r_i$ $O(1)$ $r_i$ в может быть неограниченным. $P_{i-1}$

В PDF, чтобы доказать Thm 5.1 со страницы 9, они используют Thm 3.1 со страницы 4, что усложняет задачу.

ds.algorithms cg.comp-geom domotorp
источник

Мне действительно интересно, что если я предлагаю вознаграждение, в описании которого я говорю, что ответ Джеффа мне не ясен, и в комментарии к его ответу я указываю свою проблему с ним, то почему люди продолжают отказываться от ответа на него, не отвечая на мой вопрос? Кроме того, мне интересно, получит ли его ответ награду автоматически?

Домоторп

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

Суреш Венкат

Ответы:

Ответ обновлен и переписан с нуля.

Вам предоставляется многогранник . Запуск Добкин-Kirkpatric иерархии на P. Это дает последовательность многогранников . Предположим, вы хотите найти ближайшую точку на к точке запроса . Основные начинается алгоритм вычисления по ближайшей точке к на , то он считает , что все новые регионы (палатки) , прилегающие к , найти ближайшую точку к $P$ $P_1 \subseteq P_2 \subseteq \ldots \subseteq P_k = P$ $P$ $q$ $c_1$ $q$ $P_1$ $c_1$ $c_2$ $q$ в этих новых регионах, и продолжайте в том же духе, пока мы не достигнем . $P_k$

Теперь, если находится на краю, тогда нет никаких проблем - только две палатки могут касаться этого края, или только одна из них может покрывать край. Таким образом, обновление от в этом случае занимает постоянное время. $c_i$ $c_{i+1}$ $C_i$

Поэтому проблема в том, что когда лежит в вершине высокой степени, потому что тогда число новых палаток, смежных с ней, при переходе к может быть большим. Чтобы преодолеть это, мы собираемся смоделировать вершину большой степени как набор вершин, имеющих низкую степень. В частности, на каждом этапе, если лежит в вершине , мы будем помнить два последовательных ребра смежных с , так что ближайшая точка к в $c_i$ $P_{i+1}$ $c_i$ $v$ $e_i, e_i'$ $v$ $q$ $P_{i+1}$ лежит на палатке, которая либо смежна, либо покрывает один из этих двух краев. Таким образом, мы можем выполнять необходимые вычисления за постоянное время.

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

Для этого предварительно вычислите для каждой вершины из касательное направление . Пусть - выпуклый многоугольник, который является вершиной для многоугольника (плоскость, определяющая вершину, имеет нормаль в направлении ). Концептуально, $v$ $P$ $t_v$ $Q_i(v)$ $v$ $P_i$ $t_v$ $Q_1(v), Q_2(v), ..., Q_k(v)$ ведет себя как 2d иерархия DK. Если ближайшая точка на к лежит на вершине то это соответствует и смежному ребру в , где ребро пересекает плоскость фигуры вершины в точке . Если ближайшая точка на к лежит на ребре , то вы помните два смежных ребра которые определяют две вершины (здесь $Q_i(v)$ $q$ $w$ $v$ $e$ $P_i$ $e$ $w$ $Q_i(v)$ $q$ $e'$ $P_i$ $e'$ принадлежит ). $e'$ $Q_i(v)$

И теперь мы закончили ... Действительно, если также находится на то мы можем обновить его за постоянное время (так как это просто 2d иерархия DK). Если, с другой стороны, больше не находится на то он должен принадлежать новой смежной палатке или покрывать предыдущую точку . В любом случае мы можем обновить его в постоянное время. $c_{i+1}$ $Q_{i+1}(v)$ $c_{i+1}$ $Q_{i+1}(v)$ $c_{i}$

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

Обновленный ответ. Посмотрите, имеет ли это смысл сейчас. Я так думаю об этой структуре данных. Это может не иметь никакого отношения к тому, что в статье.

Сариэль Хар-Пелед

Теперь я понимаю, спасибо! Итак, хитрость в том, что мы выбираем касательные направления в начале и сохраняем их неизменными все время! Я удалил мои предыдущие комментарии, которые были связаны с вашим старым ответом. Еще раз спасибо!

domotorp

Да. Рад был помочь!

Сариэль Хар-Пелед

Теорема 3.1 требует, чтобы иерархическое представление является компактным . Одним из требований к компактности является то, что степень в ограничена константой. Смотрите внизу страницы 3. $P$ $r_i$ $P_{i-1}$

Определение и построение иерархии Добкина-Киркпатрика намного более явны в их более ранних статьях (ссылки [9,10,11] в статье, которую вы читаете). Я настоятельно рекомендую сначала прочитать их.

Jeffε
источник

Я думаю, что они гарантируют, что степень вершин в

ограничена. Я не понимаю, как вы могли убедиться, что степень

ограничена. Например, если у вас есть многогранник, где две вершины связаны с каждой вершиной, то как вы можете начать?

P_{i - 1} ∖ P_{i}

$P_{i-1}\setminus P_i$

r_{i}

$r_i$

domotorp

С одной из других вершин, которые имеют степень 4. (Фактически, с независимым подмножеством вершин степени 4.) Точка

является вершиной

но не является вершиной

r_{i}

$r_i$

P_{i - 1}

$P_{i-1}$

P_{i}

$P_i$

Джефф

Итак, есть недоразумение. Я считаю , что

является вершиной

а в алгоритме , который я описал, в частности , ближайший к

. Я ошибаюсь?

r_{i}

$r_i$

P_{i}

$P_i$

S

$S$

Домоторп

Кажется, это одно из этих стандартных, но утомительных предположений общего положения. Если вас не волнует время выполнения, вы всегда можете заменить вершину степени

двумя чрезвычайно близкими вершинами степени

(если вы настаиваете на треугольных гранях). Повторяйте это до тех пор, пока все вершины не станут меньше 10 градусов.

d

$d$

d / 2 + 3

$d/2 + 3$

Сариэль Хар-Пелед

@Sariel: я думал так же, но тогда почему процесс закончится? Обратите внимание, что когда мы удаляем вершину, ее соседи могут не образовывать грани, поэтому нам, возможно, придется добавлять новые ребра, фактически нам, возможно, придется увеличивать степень вершины.

Домоторп

В случае, если кого-то все еще интересует вопрос: загвоздка в объяснении Добкина Кирпатрика была также указана в « Оптимальном обнаружении пересечений между выпуклыми многогранниками» Барбы и Лангермана .

Они отмечают в статье (версия SODA 2015, а не arxiv), что вычислительная геометрия О'Рурка в C , глава 7, уже детализирует обходной путь (который по сути является ответом Сариэля). Документ SODA также представляет альтернативное решение; определение варианта иерархии DK, в котором каждая вершина имеет ограниченную степень.

Джозеф Стэк
источник