Counting blanks in polygonal arrangements Journal Article


Author(s): Akopyan, Arseniy V; Segal-Halevi, Erel
Article Title: Counting blanks in polygonal arrangements
Affiliation IST Austria
Abstract: 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.
Keywords: Packing; covering; Convex objects; cake-cutting; rectilinear polygons; redivision
Journal Title: SIAM Journal on Discrete Mathematics
Volume: 32
Issue 3
ISSN: 08954801
Publisher: Society for Industrial and Applied Mathematics  
Date Published: 2018-09-06
Start Page: 2242
End Page: 2257
DOI: 10.1137/16M110407X
Open access: no
IST Austria Authors
  1. Arseniy V Akopyan
    15 Akopyan
Related IST Austria Work