Простой многоугольник

Cтраница 2

Очевидно, что Р - простой многоугольник; это следует из условия разбиения плоскости на две области и из теоремы Жордана для многоугольников ( см. разд. [16]

Лемма 6.3. Если Р - простой многоугольник без внутренних пиков, то Р - монотонный относительно у-оси многоугольник. [17]

Если чертеж состоит только из простого многоугольника, то, возможно, потребуются дополнительные построения. [18]

Когда точки являются вершинами либо простого многоугольника, либо выпуклого многоугольника, можно ожидать получить более быстрое решение. В работе [49] приведен алгоритм со сложностью О ( n log я) вычисления пары наиболее удаленных точек двух множеств и алгоритм со сложностью О ( п) решения этой же задачи для случая, когда точки каждого из множеств образуют выпуклые многоугольники. [19]

Когда точки являются вершинами либо простого многоугольника, либо выпуклого многоугольника, можно ожидать получить более быстрое решение. В работе [49] приведен алгоритм со сложностью O ( n ogn) вычисления пары наиболее удаленных точек двух множеств и алгоритм со сложностью 0 ( п) решения этой же задачи для случая, когда точки каждого из множеств образуют выпуклые многоугольники. [20]

Доказать, что во всяком простом многоугольнике можно провести диагональ, все точки которой, исключая концы, лежат внутри многоугольника. [21]

Хотя в название статьи авторы вынесли тему триангуляции простого многоугольника, в самой статье они лишь ограничились ссылкой на работы, содержащие описание сведения задачи триангуляции к задаче вычисления пар видимости. [22]

Типичный пример такой ситуации дает задача триангуляции внутренности простого многоугольника. [23]

Предположим, что алгоритм определил, что Р - простой многоугольник. [24]

Примером такой ситуации с ограничением является задача о выпуклой оболочке простого многоугольника. Заметим, что если имеется множество S кз N точек, то его всегда можно рассматривать как многоугольник, упорядочив произвольным образом точки множества и предположив, что между соседними ( с учетом цикличности) точками получившейся последовательности имеется ребро. Но что произойдет, если нам известно, что этот многоугольник простой. Определение простого многоугольника см. в разд. [25]

Отметим, однако, что теорема 6.6 не применима в случае триангуляции простого многоугольника, так как в этом случае исходно заданные ребра триангуляции уже не являются произвольными. Мы еще вернемся к этому вопросу в разд. [26]

Иллюстрация к выполнению. [27]

Разобьем многоугольник Р по прямой Lна части, каждая из которых является простым многоугольником. [28]

Область О, не содержащая бесконечно удаленной точки, односвязна, если вместе со всяким простым многоугольником, лежащим в О, она содержит и его внутренность. [29]

Это с учетом оценки сложности алгоритма вычисления пар видимости и дает суммарную оценку О ( п log log n ] сложности алгоритма триангуляции простого многоугольника. [30]

Страницы: 1 2 3 4