10.1137/16M110407X
Akopyan, Arseniy
Arseniy
Akopyan
Segal Halevi, Erel
Erel
Segal Halevi
Counting blanks in polygonal arrangements
Society for Industrial and Applied Mathematics
2018
2018-12-11T11:44:24Z
2019-08-02T12:39:04Z
journal_article
/record/58
/record/58.json
1604.00960
Inside a two-dimensional region (``cake""), there are m nonoverlapping tiles of a certain kind (``toppings""). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same ``certain kind,"" such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks.