Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного
Рассмотрена проблема покрытия многоугольников прямоугольниками, которая имеет место при подготовке
 входной информации для устройств, выполняющих изготовление фотошаблонов. Входная информация
 представляет собой описание последовательности прямоугольников. Выбор этой последовательнос...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/8123 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного / А.А. Воронов // Штучний інтелект. — 2009. — № 3. — С. 367-375. — Бібліогр.: 19 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862715040866500608 |
|---|---|
| author | Воронов, А.А. |
| author_facet | Воронов, А.А. |
| citation_txt | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного / А.А. Воронов // Штучний інтелект. — 2009. — № 3. — С. 367-375. — Бібліогр.: 19 назв. — рос. |
| collection | DSpace DC |
| description | Рассмотрена проблема покрытия многоугольников прямоугольниками, которая имеет место при подготовке
входной информации для устройств, выполняющих изготовление фотошаблонов. Входная информация
представляет собой описание последовательности прямоугольников. Выбор этой последовательности во
многом определяет производительность этих устройств и качество получаемых фотошаблонов.
Прямоугольники должны лежать полностью внутри многоугольника, и число их должно быть минимальным
или близким к минимальному. Предложен простой эвристический алгоритм, основанный на использовании
диаграммы Вороного, который покрывает многоугольник без дыр с острыми внутренними углами при
помощи прямоугольников.
Розглянуто проблему покриття багатокутників, що виникає під час підготовки вхідної інформації для
приладів, які виконують виготовлення фотошаблонів. Вхідна інформація являє собою опис послідовності
прямокутників. Вибір цієї послідовності більшою мірою визначає продуктивність цих приладів і якість
отримуваних фотошаблонів. Прямокутники повинні знаходитися повністю в середині багатокутника, і
кількість їх повинна бути мінімальною або близькою до мінімальної. Запропонований простий евристичний
алгоритм, що ґрунтується на використанні діаграми Вороного, який покриває багатокутник без дірок з
гострими внутрішніми кутами за допомогою прямокутників.
The problem of covering polygons by rectangles that take place in input data preparation for integrated circuit layout
generators is considered. Input data is the sequence of rectangles. Basically this sequence determines the productivity of
these integrated circuit layout generator and quality of output photomask. The rectangles must lie entirely within the
polygon and it is preferable to cover the polygon with as few rectangles as possible. The simple heuristic algorithm, based
on the Voronoi’s diagrams, that cover hole-free polygon with acute interior angles by rectangles is presented.
|
| first_indexed | 2025-12-07T17:54:56Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-8123 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T17:54:56Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Воронов, А.А. 2010-04-30T15:19:14Z 2010-04-30T15:19:14Z 2009 Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного / А.А. Воронов // Штучний інтелект. — 2009. — № 3. — С. 367-375. — Бібліогр.: 19 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8123 001.51:004.81 Рассмотрена проблема покрытия многоугольников прямоугольниками, которая имеет место при подготовке
 входной информации для устройств, выполняющих изготовление фотошаблонов. Входная информация
 представляет собой описание последовательности прямоугольников. Выбор этой последовательности во
 многом определяет производительность этих устройств и качество получаемых фотошаблонов.
 Прямоугольники должны лежать полностью внутри многоугольника, и число их должно быть минимальным
 или близким к минимальному. Предложен простой эвристический алгоритм, основанный на использовании
 диаграммы Вороного, который покрывает многоугольник без дыр с острыми внутренними углами при
 помощи прямоугольников. Розглянуто проблему покриття багатокутників, що виникає під час підготовки вхідної інформації для
 приладів, які виконують виготовлення фотошаблонів. Вхідна інформація являє собою опис послідовності
 прямокутників. Вибір цієї послідовності більшою мірою визначає продуктивність цих приладів і якість
 отримуваних фотошаблонів. Прямокутники повинні знаходитися повністю в середині багатокутника, і
 кількість їх повинна бути мінімальною або близькою до мінімальної. Запропонований простий евристичний
 алгоритм, що ґрунтується на використанні діаграми Вороного, який покриває багатокутник без дірок з
 гострими внутрішніми кутами за допомогою прямокутників. The problem of covering polygons by rectangles that take place in input data preparation for integrated circuit layout
 generators is considered. Input data is the sequence of rectangles. Basically this sequence determines the productivity of
 these integrated circuit layout generator and quality of output photomask. The rectangles must lie entirely within the
 polygon and it is preferable to cover the polygon with as few rectangles as possible. The simple heuristic algorithm, based
 on the Voronoi’s diagrams, that cover hole-free polygon with acute interior angles by rectangles is presented. ru Інститут проблем штучного інтелекту МОН України та НАН України Прикладные интеллектуальные системы Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного Метод покриття прямокутниками об’єктів топології мікросхем, що ґрунтується на використанні узагальненої діаграми Вороного Method for Covering of IC Layout Patterns by Rectangles Based on Voronoi’s Diagram Article published earlier |
| spellingShingle | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного Воронов, А.А. Прикладные интеллектуальные системы |
| title | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного |
| title_alt | Метод покриття прямокутниками об’єктів топології мікросхем, що ґрунтується на використанні узагальненої діаграми Вороного Method for Covering of IC Layout Patterns by Rectangles Based on Voronoi’s Diagram |
| title_full | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного |
| title_fullStr | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного |
| title_full_unstemmed | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного |
| title_short | Метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы Вороного |
| title_sort | метод покрытия прямоугольниками объектов топологии микросхем, основанный на использовании обобщенной диаграммы вороного |
| topic | Прикладные интеллектуальные системы |
| topic_facet | Прикладные интеллектуальные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8123 |
| work_keys_str_mv | AT voronovaa metodpokrytiâprâmougolʹnikamiobʺektovtopologiimikroshemosnovannyinaispolʹzovaniiobobŝennoidiagrammyvoronogo AT voronovaa metodpokrittâprâmokutnikamiobêktívtopologíímíkroshemŝogruntuêtʹsânavikoristanníuzagalʹnenoídíagramivoronogo AT voronovaa methodforcoveringoficlayoutpatternsbyrectanglesbasedonvoronoisdiagram |