Усовершенствованный метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме

Abstract

Работа посвящена доработке метода нахождения булевой фор- мулы многоугольника в дизъюнктивной нормальной форме, изло- женного в предыдущей работе автора. Усовершенствованный метод устраняет недостаток, связанный с существованием класса задач, для которых решение находится лишь приближенно. Предлагаемый метод всегда позволяет находить точное решение. Это означает, что для любой задачи элементы решения, интерпретируемые как выпуклые компоненты, будут покрывать в совокупности всю область плоскости, занимаемую многоугольником. Метод может быть использован, в частности, в системах автоматизированного проектирования топологии интегральных схем.