THE METHOD OF CONSTRUCTING A BOOLEAN FORMULA OF A POLYGON IN THE DISJUNCTIVE NORMAL FORM
Abstract
The paper focuses on finalizing the method of finding a polygon Boolean formula in disjunctive normal form, described in the previous article [1]. An improved method eliminates the drawback asso-ciated with the existence of a class of problems for which the solution is only approximate. The pro-posed method always allows to find an exact solution. The method can be used, in particular, in the systems of computer-aided design of integrated circuits topology.
About the Author
A. A. Butov
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
1. Бутов, А.А. Метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме без использования дополнительных предикатных переменных / А.А. Бутов // Вестник Брестского государственного технического университета. Физика, математика, ин-форматика. – 2012. – № 5. – С. 48–51.
2. Автоматизированная система подготовки информации для формирования фотошабло-нов / Е.А. Шестаков [и др.] // Искусственный интеллект. – 2008. – № 4. – С. 200–207.
3. Фейнберг, В.З. Геометрические задачи машинной графики больших интегральных схем / В.З. Фейнберг. – М. : Радио и связь, 1987. – 178 с.
4. Ласло, М. Вычислительная геометрия и компьютерная графика на C++ / М. Ласло. – М. : БИНОМ, 1997. – 304 с.
5. Препарата, Ф. Вычислительная геометрия : введение / Ф. Препарата, М. Шеймос. – М. : Мир, 1989. – 478 с.
6. Никулин, Е.А. Компьютерная геометрия и алгоритмы машинной графики / Е.А. Нику-лин. – СПб. : БКХ-Петербург, 2005. – 576 с.
7. Закревский, А.Д. Канонические булевы формулы многоугольников / А.Д. Закревский // Информатика. – 2009. – № 2. – С. 93–101.
8. Поттосин, Ю.В. Использование булевых функций для представления многоугольников / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управле-ние, вычислительная техника и информатика. – 2008. – № 2 (3). – С. 106–115.
9. Бутов, А.А. Простой метод нахождения булевой формулы многоугольника в дизъюнк-тивной нормальной форме / А.А. Бутов // Вестник Брестского государственного технического университета. Физика, математика, информатика. – 2011. – № 5. – С. 35–38.
Review
For citations:
Butov A.A. THE METHOD OF CONSTRUCTING A BOOLEAN FORMULA OF A POLYGON IN THE DISJUNCTIVE NORMAL FORM. Informatics. 2014;(4):117-124. (In Russ.)
Views: 681
Email this article 