Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
6. Преобразовать алгоритм построения пересечения двух выпуклых полиэдров (данный в разд. 7.3.1) в тест, проверяющий факт линейной разделимости двух полиэдров Р и Q и, если таковая обнаружена, строящий одну из разделяющих плоскостей л. Этот алгоритм должен затрачивать время, линейно зависящее от общего числа вершин в Р и Q.
ГЛАВА
Геометрия прямоугольников
Методы, которые были ранее разработаны для задач о пересечении плоских выпуклых многоугольников, безусловно, применимы и к прямоугольникам. Точно так же набор отрезков, каждый из которых параллелен или перпендикулярен любому другому элементу из этого набора, можно обработать обычными методами решения задач о пересечениях, которые были описаны в предыдущих главах. Однако весьма специальный вид отрезков, параллельных ровно двум ортогональным прямым, или прямоугольников, сторонами которых являются подобные отрезки, заставляет предположить, что можно разработать и более эффективные методы, учитывающие специфику этих в высшей степени структурированных случаев. А в процессе изучения задач этого класса можно приобрести более глубокое понимание геометрических свойств, которыми обладают вышеупомянутые объекты — прямоугольники и ортогональные отрезки, — а также охарактеризовать более широкий класс задач, к которым применимы указанные методы.
Все это было бы интересным, хотя и довольно бесполезным упражнением, если бы прямоугольники и ортогональные отрезки не являлись важнейшими компонентами многих приложений, часть из которых обладает чрезвычайной важностью в области современных передовых технологий, особенно в области цифровых схем с очень высоким уровнем интеграции (СБИС). Поэтому, перед тем как начать подробное обсуждение алгоритмического материала, стоит потратить немного времени на описание ряда важных приложений.
8.1. Некоторые приложения геометрии прямоугольников
8.1.1. Проектирование СБИС
Фотошаблоны, используемые при изготовлении интегральных схем, зачастую представляют собой наборы прямоугольников, стороны которых параллельны двум взаимно орто-
8.1. Некоторые приложения геометрии прямоугольников
395
тональным направлениям. Каждый из этих прямоугольников является или участком проводника, или областью ионной имплантации, или межслойным контактом и т. п., как показано на рис. 8.1 [Lauther (1978); Baird (1978); Mead, Conway (1979)].
- 1
- 1 ¦
- 1
д
"~B:
- 1
Щ
- 1
1
i
1
1
i
1
1
1
Рис. 8.1. Типичная геометрия одной интегральной схемы.
Эти прямоугольники размещаются на плоскости в соответствии с конкретными техническими требованиями, которые определяют минимальные зазоры между одними типами прямоугольников, минимальные наложения для других типов и т. д. Условия на зазоры и наложения возникают из-за конфликтующих требований минимизировать общую используемую
Рис. 8.2. Проверить величину минимального зазора X вокруг прямоугольника R можно путем расширения R во все стороны на Я (для формирования R') и контроля наложений.
площадь (это очевидное экономическое ограничение) и выполнить необходимые электрические условия (изоляцию или контакт) с учетом возможных отклонений при производстве. (Очевидно, что, чем меньше зазор, тем больше вероятность возникновения нежелательного контакта.)
Следовательно, важнейшей задачей при проектировании фотошаблонов ИС (интегральных схем) является проверка выполнения проектных норм, или, выражаясь иначе, «контроль соблюдения проектных норм». На рис. 8.2 показан пример того,
Гл. 8. Геометрия прямоугольников
как можно проверить нарушение минимальной величины К зазора между прямоугольником R- и соседствующими с ним прямоугольниками. Для этого можно увеличить R, добавив к нему полосу ширины %, и проверить, не будет ли увеличенный прямоугольник R' пересекаться с какими-нибудь из своих соседей. Значит, задача проверки зазора преобразуется в задачу о пересечении прямоугольников. Разновидности подобного подхода можно использовать при проверке выполнения и других технических требований, таких как наложения, покрытия и т. п.
В то время как описанные выше этапы связаны в определенном смысле с «синтаксической» корректностью фотошаблона, другая важная задача заключается в проверке того, что
Рис. 8.3. Определение компонент связности на множестве прямоугольников можно использовать при решении задачи выделения электрических цепей.
фотошаблон функционально корректно реализует заданную схему. Первым этапом этой задачи является интерпретация геометрии фотошаблона как электрической схемы, т. е. идентификация таких подмножеств прямоугольников, все элементы которых электрически связаны. Такая работа называется восстановлением принципиальной схемы. Выражаясь несколько более абстрактными терминами, можно представить себе граф, вершины которого соответствуют прямоугольникам и такой, что пара вершин соединена ребром, если соответствующие прямоугольники имеют непустое пересечение. В такой формулировке восстановление принципиальной схемы сводится к задаче обнаружения компонент связности данного графа. Однако выделение компонент связности дает несколько меньше информации, чем требуется для указанного восстановления, поскольку на самом деле нужно очертить границу (так называемый контур) каждой компоненты связности (рис. 8.3).
