Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Условия безопасности и отсутствия тупиков хорошо видны на диаграмме транзакций к базе данных. Прежде всего, кривая,
400
Гл. 8. Геометрия прямоугольников
изображающая расписание, не может заходить внутрь объединения прямоугольников транзакций. Это объединение будет представлять собой набор компонент связности (рис. 8.5). Но одно это условие не гарантирует, что в системе будут отсутствовать тупики. На самом деле нужно описать некую область, содержащую прямоугольники транзакций и такую, что в любом расписании (т. е. в любой монотонно неубывающей кривой), внешнем по отношению к ней, не было бы тупиков. Такая область показана на рис. 8.5, где заштрихованные области были добавлены к объединению прямоугольников транзакций. Теперь интуитивно ясно, что подобное расширение объединения прямоугольников удовлетворяет заданному требованию. Эта область называется ЮЗ-замыканием (юго-западным замыканием) объединения прямоугольников [Yannakakis, Papadimit-riou, Kung (1979); Lipski, Papadimitriou (1981); Soisalong Soininen, Wood (1982)] и будет строго определена в разд. 8.6.
8.2. Область применения результатов
Хотя наборы прямоугольников и были исходными объектами, вызвавшими большую часть объема исследовательской работы в данной области, и практически все результаты формулируются в терминах взаимно ортогональных направлений (обычно координатных осей), было бы уместно попытаться именно сейчас определить максимальную сферу применения данной теории.
Начнем с рассмотрения двух наборов Si и S2, каждый из которых содержит параллельные отрезки, причем направления отрезков из Si и S2 взаимно ортогональны. Прямые, несущие эти отрезки, образуют сетку на плоскости. Представим теперь точки в однородных координатах (хи х2, хг) (см. разд. 1.3.2 и 7.3.2) и применим к точкам этой плоскости обычное невырожденное преобразование проецирования, т. е. преобразование, описываемое невырожденной матрицей третьего порядка ?Ф. Хорошо известно (см., например, [Ewald (1971)] или [Birkhoff, MacLane (1965)]), что это преобразование переводит точки в точки, а прямые в прямые и сохраняет инцидентность, т. е. любое такое преобразование не меняет структуру сетки. Если матрица з& имеет вид
0 0 | а
где ^ — невырожденная матрица второго порядка, и а ф 0, то прямая на бесконечности переходит сама в себя, а два на-
8.2. Область применения результатов
401
правления, которые были вначале ортогональны, становятся теперь произвольными. Если же невырожденная матрица s& не обладает блочной формой, то одна или обе точки, лежащие на бесконечности на двух указанных исходных направлениях, перейдут в конечные точки, причем пропадает даже свойство параллельности прямых в каждом из наборов. Одна из типичных ситуаций такого рода показана на рис. 8.6.
Приведенные соображения, по сути, характеризуют область применения так называемой геометрии прямоугольников и приводят к следующим определениям:
Определение 8.1. Множество четырехугольников М называется изоте-тичным1), если стороны каждого из элементов 31 принадлежат одному из двух пучков прямых линий с центрами в точках р\ и р2 соответственно (pi и р2 могут принадлежать прямой на бесконечности в этой плоскости), и все элементы Ж лежат полностью по одну сторону от прямой, проходящей через точки рх и р2.
После этого пояснения для простоты представления далее будем рассматривать тот случай, когда р\ и р2 определяют ортогональные направления.
!) «Изотетичные» означает «одинаково расположенные» от греческих слов isos (одинаковый) и tithenai (располагать). Существует заметная терминологическая неопределенность данного понятия между оценками цонятий «прямолинейные», «ортогональные», «выравненные», «изоориентированные». Хотя смыслы последних понятий однозначны (за исключением, вероятно, понятия «прямолинейные»), понятие «изотетичные» по смыслу ближе всего
Рис. 8.6. Пример невырожденного проективного преобразования применительно к плоской фигуре, образованной ортогональными отрезками.
402
Гл. 8. Геометрия прямоугольников
Алгоритмы, о которых будет идти речь в данной главе, связаны с определением различных свойств множеств прямоугольников (или ортогональных отрезков). Можно предложить одну фундаментальную классификацию этих алгоритмов, зависящую от базисного типа операций, т. е. зависящую от того, будем ли мы работать в статической или динамической среде. В первом случае вся информация, необходимая для решения задачи, полностью известна до начала вычислений; во втором случае допустимы также динамические корректировки данных путем операций вставки и удаления.
Операции этих двух типов — статические и динамические — подразумевают, как и следовало ожидать, использование существенно различающихся структур данных. В то время как работа в статическом режиме в настоящее время хорошо изучена, исследование более сложных динамических операций пребывает в стадии активного развития. Поэтому целесообразно дать здесь детальное описание алгоритмов именно статического типа; отсылки к продолжающимся исследованиям алгоритмов динамического типа будут приведены в конце настоящей главы.
