РАЗБИЕНИЕ ПЛОСКОСТИ РЕГУЛЯРНОЙ СИСТЕМОЙ КРИВЫХ

В вопросах вычислительной геометрии и автоматического проектирования электрических схем существенную роль играют задачи разбиения евклидовой плоскости конечной системой непрерывных плоских кривых (линий) заданной формы. Зачастую эта система имеет однородную структуру, и кривые могут иметь одинаковое число попарно взаимных пересечений. Каждая кривая состоит из внутренних и, самое большее, двух концевых точек. В статье рассматриваются четыре типа кривых: ограниченные, полуограниченные, неограниченные или замкнутые (циклические). В соответствии с этим определяются ограниченная, полуограниченная, неограниченная и замкнутая (циклическая) системы кривых. Определяется также понятие k-регулярной системы линий: каждая пара линий из этой системы пересекается ровно в k точках. Доказывается теорема, в которой находится наибольшее число областей (частей) плоскости, которая разбивается kрегулярной системой из n кривых для случаев, когда система является ограниченной, полуограниченной, неограниченной или замкнутой (циклической). Следствием этой теоремы является нахождение наибольшего числа областей, на которые разбивается плоскость n отрезками, лучами, прямыми, ограниченными (полуограниченными или неограниченными) углами, полуокружностями, окружностями, эллипсами, параболами, треугольниками, четырехугольниками, выпуклыми m-угольниками. В некоторых практических вопросах проектирования на плоскости кривые могут иметь форму ломаных линий. Доказательство теоремы проводится на довольно доходчивом языке теории графов, методы которой широко используются во многих прикладных задачах физики, химии, биологии, географии, экономики, социологии, лингвистики и электротехники (в частности, при проектировании электрических схем). Существенным в доказательстве является то, что можно рассматривать возможность построения системы плоских кривых требуемой формы, которая будет k-регулярной.