On complexity of envelopes of piecewise linear functions, unions and intersections of polygons

Pavel Kozhevnikov

We prove tight upper bounds for the number of vertices of a simple polygon that is the union or the intersection of two simple polygons with given numbers of convex and concave ver…