Counting Blanks in Polygonal Arrangements

DOI10.1137/16M110407XzbMATH Open1397.52009arXiv1604.00960OpenAlexW2787428120WikidataQ129285814 ScholiaQ129285814MaRDI QIDQ4585744FDOQ4585744

Authors: Arseniy Akopyan, Erel Segal-Halevi 

Publication date: 7 September 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Inside a two dimensional region ("cake"), there are $m$ non-overlapping tiles of a certain kind ("toppings"). We want to expand the toppings while keeping them non-overlapping, 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 axes-parallel rectangles. (4) The cake is an axes-parallel rectilinear polygon and the toppings are axes-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks.

Full work available at URL: https://arxiv.org/abs/1604.00960

Recommendations

• Counting \(k\)-convex polyominoes
• scientific article; zbMATH DE number 1357398
• Counting configurations in designs
• Enumeration of polyominoes inscribed in a rectangle
• Polytopes in arrangements
• Counting figures in planar random configurations
• Counting corners in partitions

zbMATH Keywords

packing and coveringcake-cuttingrectilinear polygonsconvex objectsredivision

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Cites Work

• On the perimeter of \(k\) pairwise disjoint convex bodies contained in a convex set in the plane
• Title not available (Why is that?)
• Covering convex sets with non-overlapping polygons
• Graph-Theoretic Solutions to Computational Geometry Problems

This page was built for publication: Counting Blanks in Polygonal Arrangements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4585744)