Counting blanks in polygonal arrangements

Akopyan A, Segal Halevi E. 2018. Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. 32(3), 2242–2257.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Akopyan, ArseniyISTA ; Segal Halevi, Erel
Department
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.
Publishing Year
Date Published
2018-09-06
Journal Title
SIAM Journal on Discrete Mathematics
Publisher
Society for Industrial and Applied Mathematics
Volume
32
Issue
3
Page
2242 - 2257
IST-REx-ID
58

Cite this

Akopyan A, Segal Halevi E. Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. 2018;32(3):2242-2257. doi:10.1137/16M110407X
Akopyan, A., & Segal Halevi, E. (2018). Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/16M110407X
Akopyan, Arseniy, and Erel Segal Halevi. “Counting Blanks in Polygonal Arrangements.” SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics , 2018. https://doi.org/10.1137/16M110407X.
A. Akopyan and E. Segal Halevi, “Counting blanks in polygonal arrangements,” SIAM Journal on Discrete Mathematics, vol. 32, no. 3. Society for Industrial and Applied Mathematics , pp. 2242–2257, 2018.
Akopyan A, Segal Halevi E. 2018. Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. 32(3), 2242–2257.
Akopyan, Arseniy, and Erel Segal Halevi. “Counting Blanks in Polygonal Arrangements.” SIAM Journal on Discrete Mathematics, vol. 32, no. 3, Society for Industrial and Applied Mathematics , 2018, pp. 2242–57, doi:10.1137/16M110407X.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 1604.00960

Search this title in

Google Scholar