TY - GEN
T1 - Cutting polygons into small pieces with chords
T2 - 28th Annual European Symposium on Algorithms, ESA 2020
AU - Arkin, Esther M.
AU - Das, Rathish
AU - Gao, Jie
AU - Goswami, Mayank
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
AU - Tóth, Csaba D.
N1 - Funding Information:
Funding This research was partially supported by NSF grants CCF-1439084, CCF-1540890, CCF-1617618, CCF-1716252, CCF-1725543, CCF-1910873, CCF-2007275, CNS-1618391, CNS-1938709, CRII-1755791, CSR-1763680, DMS-1737812, DMS-1800734, and OAC-1939459. The authors also acknowledge partial support from the US-Israel Binational Science Foundation (project 2016116), the DARPA Lagrange program, the Sandia National Labs and grants by the Swedish Transport Administration and the Swedish Research Council.
Publisher Copyright:
© Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth
PY - 2020/8/1
Y1 - 2020/8/1
N2 - Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the “size” of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
AB - Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the “size” of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
KW - Arrangements
KW - Localization
KW - Polygon partition
KW - Visibility
UR - http://www.scopus.com/inward/record.url?scp=85092534413&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092534413&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2020.7
DO - 10.4230/LIPIcs.ESA.2020.7
M3 - Conference contribution
AN - SCOPUS:85092534413
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 28th Annual European Symposium on Algorithms, ESA 2020
A2 - Grandoni, Fabrizio
A2 - Herman, Grzegorz
A2 - Sanders, Peter
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 7 September 2020 through 9 September 2020
ER -