Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
8.10. Упражнения
453
одним примером такой задачи является задача о ПОИСКЕ ПЕРЕСЕЧЕНИЙ С ОРТОГОНАЛЬНЫМИ ОТРЕЗКАМИ, в которой требуется найти среди N заданных горизонтальных и вертикальных прямолинейных отрезков все пересекающие заданный ортогональный запросный отрезок. Эту задачу исследовали Вайшнави и Вуд [Vaishnavi, Wood (1982)], предложившие алгоритм, который обладает следующими оценками: по времени запроса — 0(\ogN -f К), а по времени предварительной обработки и по памяти — 0(N log N). Оценку по памяти можно снизить до в (Л/) [Chazelle (1983с)]. Для случая, когда в данной задаче разрешены вставки и удаления отрезков, Мак-крейт предложил динамическую структуру данных [McCreight (1981) ], которая требует О (N) памяти и О (log2 N + К) времени, где O(N) выражает мощность множества различных значений координат. Для этого же случая Липски и Пападимитриу [Lipski, Papadimitriou (1981)] предложили алгоритм с оценками по времени — О (log N-log log N + К), а по памяти — О (NlogN). Недавно Эдельсбруннер и Маурер [Edelsbrunner, Maurer (1981)] унифицировали некоторые из ранее упомянутых методов решения данного класса задач о поиске пересечений и получили следующие результаты. Для задач статического типа существует структура данных, обеспечивающая следующие оценки эффективности: для времени запроса — O(logd~' N + К), для времени предварительной обработки и памяти — по 0(N\ogdN). Оценка по памяти позднее была доведена до 0(N logd-! N-\og logiV) [Ghazelle, Guibas (1984)]. Что же касается динамического случая, то существует динамическая структура данных, обеспечивающая следующие оценки эффективности: для времени запроса — 0(logdN + К), для памяти— 0(N\ogdN), для времени корректировки—0(logdiV) [Edelsbrunner (1980)].
8.10. Упражнения
1. Дано множество нетривиальных цепей для объединения, состоящего из N изотетичных прямоугольников. Построить алгоритм, который выбирает среди них цепи, формирующие нетривиальный контур. (Цель состоит в получении алгоритма с оценкой по времени 0{N log N).)
2. ТРЕХМЕРНОЕ ДОМИНИРОВАНИЕ. Дано множество из N точек в Е3. Создать алгоритм, находящий s пар доминирования за время 0(N log N + s) с затратой B(N) памяти.
3. ТРЕХМЕРНОЕ ДОМИНИРОВАНИЕ. Доказать, что нижней оценкой времени, необходимого для поиска пар доминирования среди N точек в Е3, является Q(N log N+s).
4. Охваты квадратов. Задачу об ОХВАТАХ КВАДРАТОВ можно получить заменой слова «прямоугольник» словом «квадрат» в формулировке за-
454
Гл. 8. Геометрия прямоугольников
дачи 0.10. Показать, что задача об ОХВАТАХ КВАДРАТОВ эквивалентна задаче о ТРЕХМЕРНОМ ДОМИНИРОВАНИИ.
5. Показать, что задача о СЛИЯНИИ ДОМИНИРОВАНИИ в Е\ определенная на множестве, состоящем из N точек, может быть решена за время О(N log2 N + s), где s число обнаруженных пар.
6. Маршрут в лабиринте. Лабиринт образован двумя наборами отрезков (в сумме их N штук), каждый из которых содержит параллельные отрезки (для простоты будем считать, что направления отрезков из разных наборов ортогональны). Лабиринт разбивает плоскость на связные области. Для двух заданных на плоскости точек s и t маршрутом называется соединяющая их кривая, не пересекающая ни одного заданного отрезка.
(a) Построить алгоритм, проверяющий факт существования маршрута,
(b) Построить алгоритм, соединяющий s и t маршрутом (если таковой существует).
Литература1
'А. V. Aho, J. Е. Hopcroft and J. D. Ullman, The Design and Analysis of Computer
Algorithms, Addison-Wesley, Reading, Mass., 1974. Z9S. B. Akers, Routing, in Design Automation of Digital Systems, M. Breuer, ed.,
Prentice-Hall, Englewood Cliffs, NJ, 1972. S. G. Akl, Two remarks on a convex hull algorithm, Info. Proc. Lett. 8,108-109 (1979). S. G. Akl and G. T. Toussaint, Efficient convex hull algorithms for pattern recognition
applications, Proc. 4th Int'l Joint Conf. on Pattern Recognition, Kyoto, Japan, pp.
483-487 (1978).
A. M. Andrew, Another efficient algorithm for convex hulls in two dimensions, Info.
Proc. Lett. 9, 216-219(1979). H. C. Andrews, Introduction to Mathematical Techniques in Pattern Recognition,
Wiley-Interscience, New York, 1972. M. J. Atallah, A linear time algorithm for the Hausdorff distance between convex
polygons, Info. Proc. Lett. 8, 207-209 (Nov. 1983). D. Avis, On the complexity of finding the convex hull of a set of points, McGill
University, School of Computer Science; Report SOCS 79.2, 1979 D. Avis and В. K. Bhattacharya, Algorithms for computing d-dimensional Voronoi
diagrams and their duals, in Advances in Computing Research. Edited by F. P.
Preparata. 1, JAI Press, 159-180(1983). H. S. Baird, Fast algorithms for LSI artwork analysis, Design Automation and Fault-Tolerant Computing, 2, 179-209 (1978). R. E. Barlow, D. J. Bartholomew, J. M. Bremner and H..D. Brunk, Statistical
Inference under Order Restrictions, Wiley, New York, 1972. M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th ACM Annual
Symp. on Theory ofComput., pp. 80-86 (May 1983). R. V. Benson, Euclidean Geometry and Convexity, McGraw-Hill, New York, 1966. J. L. Bentley, Multidimensional binary search trees used for associative searching,
