Search
Метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме без использования дополнительных предикатных переменных
View/
Date
2012Publisher
БрГТУUDC
004.5Citation
Бутов, А. А. Метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме без использования дополнительных предикатных переменных / А. А. Бутов // Вестник БрГТУ. Серия : Физика, математика, информатика. – 2012. – № 5. – С. 22–25.Abstract
Предложен приемлемый на практике метод решения задачи построения булевой формулы многоугольника в дизъюнктивной нормальной форме. Метод основан на последовательном формировании выпуклых компонентов, которые представляют в искомой формуле отдельные элементарные конъюнкции и покрывают в совокупности
все точки плоскости, принадлежащие исходному многоугольнику.
Достоинством метода является присутствие в полученной формуле только тех предикатных переменных, которые связаны с полуплоскостями, порождаемыми лишь сторонами многоугольника.
Метод может быть использован, в частности, в системах автоматизированного проектирования топологии интегральных схем.
Annotation in another language
A feasible in practice method of the solution of the constructing a Boolean formula of a polygon in the disjunctive normal form is proposed. The
method is based on a sequential formation of convex components, which represent in the desired formula individual elementary conjunctions and cover
in aggregate all the points of the plane belonging to the original polygon.
The advantage of the method is the presence in the resulting formula only the predicate variables that are associated with the half-planes generated
only by the sides of the polygon.
The method can be used, in particular, in the systems computer-aided design of integrated circuits topology.
Collection
- 2012 [20]
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция-Некоммерчески») 4.0 Всемирная.