Аннотация:
Для практических приложений важно оценивать сложность операции пересечения/объединения фигур на плоскости, ограниченных замкнутым ломаными без самопересечений. Если фигуры выпуклые, то сложность пересечения находится легко. Однако, если фигуры не являются выпуклыми, то задача становится более содержательной. В докладе будут обсуждаться известные оценки сложности пересечения фигур, в частности точные оценки для сложности пересечения двух многоугольников с данным количеством вершин, в которых угол больше/меньше развернутого.
|
