Cutting polygons into small pieces with chords: Laser-based localization

Esther M. Arkin; Rathish Das; Jie Gao; Mayank Goswami; Joseph S.B. Mitchell; Valentin Polishchuk; Csaba D. Tóth

doi:10.4230/LIPIcs.ESA.2020.7

Cutting polygons into small pieces with chords: Laser-based localization

Esther M. Arkin
, Rathish Das
, Jie Gao
, Mayank Goswami
, Joseph S.B. Mitchell
, Valentin Polishchuk
, Csaba D. Tóth

Applied Mathematics and Statistics

Stony Brook University

Stony Brook University
Rutgers - The State University of New Jersey, New Brunswick
City University of New York
Linköping University
California State University Northridge
Tufts University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

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.

Original language	English
Title of host publication	28th Annual European Symposium on Algorithms, ESA 2020
Editors	Fabrizio Grandoni, Grzegorz Herman, Peter Sanders
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959771627
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2020.7
State	Published - Aug 1 2020
Event	28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy Duration: Sep 7 2020 → Sep 9 2020

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	173

Conference

Conference	28th Annual European Symposium on Algorithms, ESA 2020
Country/Territory	Italy
City	Virtual, Pisa
Period	09/7/20 → 09/9/20

Keywords

Arrangements
Localization
Polygon partition
Visibility

Access to Document

10.4230/LIPIcs.ESA.2020.7

Cite this

Arkin, E. M., Das, R., Gao, J., Goswami, M., Mitchell, J. S. B., Polishchuk, V., & Tóth, C. D. (2020). Cutting polygons into small pieces with chords: Laser-based localization. In F. Grandoni, G. Herman, & P. Sanders (Eds.), 28th Annual European Symposium on Algorithms, ESA 2020 Article 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 173). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2020.7

Arkin, Esther M. ; Das, Rathish ; Gao, Jie et al. / Cutting polygons into small pieces with chords : Laser-based localization. 28th Annual European Symposium on Algorithms, ESA 2020. editor / Fabrizio Grandoni ; Grzegorz Herman ; Peter Sanders. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{8157b26049f14a3faec8f6df62e9a00f,

title = "Cutting polygons into small pieces with chords: Laser-based localization",

abstract = "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.",

keywords = "Arrangements, Localization, Polygon partition, Visibility",

author = "Arkin, \{Esther M.\} and Rathish Das and Jie Gao and Mayank Goswami and Mitchell, \{Joseph S.B.\} and Valentin Polishchuk and T{\'o}th, \{Csaba D.\}",

note = "Publisher Copyright: {\textcopyright} Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. T{\'o}th; 28th Annual European Symposium on Algorithms, ESA 2020 ; Conference date: 07-09-2020 Through 09-09-2020",

year = "2020",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.ESA.2020.7",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Fabrizio Grandoni and Grzegorz Herman and Peter Sanders",

booktitle = "28th Annual European Symposium on Algorithms, ESA 2020",

}

Arkin, EM, Das, R, Gao, J, Goswami, M, Mitchell, JSB, Polishchuk, V & Tóth, CD 2020, Cutting polygons into small pieces with chords: Laser-based localization. in F Grandoni, G Herman & P Sanders (eds), 28th Annual European Symposium on Algorithms, ESA 2020., 7, Leibniz International Proceedings in Informatics, LIPIcs, vol. 173, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 28th Annual European Symposium on Algorithms, ESA 2020, Virtual, Pisa, Italy, 09/7/20. https://doi.org/10.4230/LIPIcs.ESA.2020.7

Cutting polygons into small pieces with chords: Laser-based localization. / Arkin, Esther M.; Das, Rathish; Gao, Jie et al.
28th Annual European Symposium on Algorithms, ESA 2020. ed. / Fabrizio Grandoni; Grzegorz Herman; Peter Sanders. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 173).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 - 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 - https://www.scopus.com/pages/publications/85092534413

U2 - 10.4230/LIPIcs.ESA.2020.7

DO - 10.4230/LIPIcs.ESA.2020.7

M3 - Conference contribution

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 -

Arkin EM, Das R, Gao J, Goswami M, Mitchell JSB, Polishchuk V et al. Cutting polygons into small pieces with chords: Laser-based localization. In Grandoni F, Herman G, Sanders P, editors, 28th Annual European Symposium on Algorithms, ESA 2020. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2020. 7. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ESA.2020.7

Cutting polygons into small pieces with chords: Laser-based localization

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this