论文标题
将多边形切成带有和弦的小块：基于激光的本地化
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization
论文作者
论文摘要
由Tripwire激光器的室内定位促进，我们研究了使用多边形和弦将多边形切成小型零件的问题。考虑了几种版本，具体取决于作品的“大小”的定义。特别是，我们将最大刻有圆圈的面积，直径和半径视为一块大小的量度。我们还考虑了不同的目标，要么最小化给定数量的和弦的最大尺寸，要么最大程度地减少了达到给定尺寸阈值的和弦数量。我们为具有孔的多边形和近似算法给出了硬度结果。
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.
