2026-07-20T11:14:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12873 2024-03-06T10:50:57Z ddc:004 open_access

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization Arkin, Esther M. Das, Rathish Gao, Jie Goswami, Mayank Mitchell, Joseph S. B. Polishchuk, Valentin Tóth, Csaba D. Polygon partition Arrangements Visibility Localization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther M. Arkin and Rathish Das and Jie Gao and Mayank Goswami and Joseph S. B. Mitchell and Valentin Polishchuk and Csaba D. Tóth 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.7 urn:nbn:de:0030-drops-128736 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.7 eng https://creativecommons.org/licenses/by/3.0/legalcode