Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Еще один класс задач о пересечениях, к которому, в частности, относится задача о пересечении отрезков, представленная в разд. 7.2.3, это отчет обо всех К пересекающихся парах на множестве из N объектов. Цель состоит в разработке алгоритмов, время работы которых равнялось бы 0(f(N) + К), т. е. оно содержит фиксированную верхнюю оценку 0(f(N)), а кроме того, пропорционально размеру искомого подмножества. В алгоритме из разд. 7.2.3 эта цель не достигается, поскольку оценка времени его работы равна О ((К + ./V) log N), а соответствующая нижняя оценка для данной задачи равна Q(K + N logyV). Это несовпадение оценок, привело к большой исследовательской работе. Поскольку была широко распространена уверенность в том, что несовпадение оценок объясняется скорее неэффективностью предложенного алгоритма, чем неадекватностью нижней оценки, то велся поиск более эффективных методов решения для частных случаев задачи, когда на отрезки налагаются некоторые ограничения. Первый
') Это — сокращение словосочетания «полиномиально-логарифмический» и относится к оценкам вида 0(\ogcn). — Прим. перев.
390
Гл. 7. Пересечения
шаг в этом направлении был сделан Нивергельтом и Препара-той [Nievergelt, Preparata (1982)], которые рассмотрели пересечение двух плоских карт (случай, когда отрезками являются ребра двух планарных графов, уложенных на плоскости); они показали, что если грани каждого из графов выпуклы, то достижима оценка по времени О (N log N + К). Фактически требование выпуклости не обязательно, как следует из более позднего результата, полученного Мэйрсоном и Столфи [Mairson, Stolfi (1983)]: пересечение двух наборов А я В, каждый из которых состоит из непересекающихся отрезков, и таких, что |Л| + |?| = М, можно определить за время О {N log N + К), где К — число пересечений. Еще один пример задач подобного рода возникает, когда каждый набор (Л и В) содержит параллельные отрезки; очень простой метод решения этой задачи, обладающий такой же временной оценкой, будет изложен в гл. 8. Все эти методы относятся к типу плоского заметания; для них в общем случае операция динамической вставки точки пересечения в список точек событий требует О (К log К) времени. Полностью отказавшись от использования методов типа заметающей прямой, Чазелле [Chazelle (1983а)] предложил алгоритм для пересечения отрезков, основанный на иерархическом подходе и требующий О (К + N log2 N/\og log N) времени. Затем Чазелле и Эдельсбруннер IChazelle, Edelsbrunner (1988)] предложили алгоритм решения данной задачи с оптимальной оценкой по времени равной О (N log N -+- К). Этот алгоритм является оригинальной комбинацией ряда известных методов, таких как плоское заметание, деревья отрезков, топологическое заметание, амортизация затрат и т. д. Хотя основным методом здесь по-прежнему осталось плоское заметание, однако, алгоритм поддерживает не просто статус заметающей прямой, а скорее всю сцену справа от нее, образованную пересекающими ее отрезками. В отличие от близкого к оптимальности алгоритма Бентли — Оттмана, использующего 0(N) памяти, в обсуждаемом алгоритме используется 0(N-\-K) памяти. Следовательно, вопрос о возможности одновременного достижения оптимальных оценок по времени памяти остается открытым.
Если вместо перечисления пересечений N отрезков требуется просто получить их число (подсчет числа пересечений отрезков), то задача существенно изменяется. Существует очевидная преобразуемость этих двух задач, поскольку любой алгоритм перечисления пересечений можно использовать для решения соответствующей задачи подсчета; однако эффективность может ухудшиться, так как число пересечений К может достигать величины B(N2). Лучшим результатом, не зависящим от К среди известных на сей день, является алгоритм, принад-
7.4. Замечания и комментарии
391
лежащий Чазелле [Chazelle (1983а)], который требует 0(Л/1'695 log Л') времени и использует линейную память.
В разд. 7.2.3.2 было показано, что для определения факта отсутствия пересечений среди N отрезков на плоскости достаточно Q(yVlogA0 операций. Что произойдет, если потребовать, чтобы эти N отрезков были ребрами какого-нибудь многоугольника? В этом случае задача определения пересечения сводится к проверке простоты многоугольника, и было бы интересно исследовать вопрос о том, приводит ли это дополнительное условие к упрощениям алгоритма. По сей день для задачи о ПРОВЕРКЕ ПРОСТОТЫ МНОГОУГОЛЬНИКА не удается дать оценку сложности. Недавно появилось сообщение о прогрессе в решении близкой задачи о ПЕРЕСЕЧЕНИИ РЕБЕР МНОГОУГОЛЬНИКА; для заданного N-угольника Р требуется перечислить все его ребра, которые пересекаются (с какими-нибудь другими ребрами). Для этой задачи необходимо Q(N\ogN) операций, как показал Яромчик, используя общую теорию Бен-Ора [Jaromczyk (1984)]. К сожалению, эта оценка не повлияла на оценку сложности решения задачи о ПРОВЕРКЕ ПРОСТОТЫ МНОГОУГОЛЬНИКА, поскольку преобразование последней к задаче о ПЕРЕСЕЧЕНИИ РЕБЕР МНОГОУГОЛЬНИКА направлено в обратную сторону. Поэтому вопрос об оценке сложности задачи о ПРОВЕРКЕ ПРОСТОТЫ МНОГОУГОЛЬНИКА остается замечательной нерешенной проблемой вычислительной геометрии.
