文章基本信息

标题：Cutting Polygons into Small Pieces with Chords: Laser-Based Localization
本地全文：下载
作者：Esther M. Arkin ; Rathish Das ; Jie Gao 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：7:1-7:23
DOI：10.4230/LIPIcs.ESA.2020.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Polygon partition; Arrangements; Visibility; Localization