论文标题
将多边形划分为小块
Partitioning a Polygon Into Small Pieces
论文作者
论文摘要
我们研究将给定简单的多边形$ p $划分为最少数量的连接多边形零件的问题，每个零件的大小。我们描述了一种用于构建此类分区的通用技术，该分区适用于几个“有限尺寸”的概念，即每个部分都必须包含在轴对准或任意旋转的单元平方或单位磁盘中，或者每个零件的周围，直线直径或地球直径。这些问题是由制造，有限元分析，碰撞检测，车辆路线，运输和激光捕获微异构的实际设置所激发的。 已知应将每个作品包含在轴线对准的单元正方形中的版本已知NP-HARD [ABRAHAMSEN和Stade，Focs，2024]，而其他版本似乎并不容易。我们的主要结果是开发恒定的因子近似算法，这意味着生产分区中的碎片数量最多是恒定因子大于最佳分区的基数。现有的算法[Damian和Pemmaraju，Algorithmica，2004年]不允许Steiner积分，这意味着生产的所有角落的所有角落也必须是$ P $的角。这具有令人失望的结果，即通常不存在分区，而我们的算法总是会产生有意义的分区。此外，没有Steiner点的最佳分区可能需要$ω（n）$零件，其中$ n $ corners的多边形零件可能需要在允许施泰纳点时仅包含$ 2 $的分区。其他现有的算法[Arkin，Das，Gao，Goswami，Mitchell，Polishell，Polishuk和Tóth，Esa，2020年]只允许沿和弦分开$ P $（并旨在最大程度地减少和弦的数量而不是零件的数量），而我们对碎片的边界不做任何约束。
We study the problem of partitioning a given simple polygon $P$ into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for constructing such partitions that works for several notions of `bounded size,' namely that each piece must be contained in an axis-aligned or arbitrarily rotated unit square or a unit disk, or that each piece has bounded perimeter, straight-line diameter or geodesic diameter. The problems are motivated by practical settings in manufacturing, finite element analysis, collision detection, vehicle routing, shipping and laser capture microdissection. The version where each piece should be contained in an axis-aligned unit square is already known to be NP-hard [Abrahamsen and Stade, FOCS, 2024], and the other versions seem no easier. Our main result is to develop constant-factor approximation algorithms, which means that the number of pieces in the produced partition is at most a constant factor larger than the cardinality of an optimal partition. Existing algorithms [Damian and Pemmaraju, Algorithmica, 2004] do not allow Steiner points, which means that all corners of the produced pieces must also be corners of $P$. This has the disappointing consequence that a partition often does not exist, whereas our algorithms always produce meaningful partitions. Furthermore, an optimal partition without Steiner points may require $Ω(n)$ pieces for polygons with $n$ corners where a partition consisting of just $2$ pieces exists when Steiner points are allowed. Other existing algorithms [Arkin, Das, Gao, Goswami, Mitchell, Polishchuk and Tóth, ESA, 2020] only allow $P$ to be split along chords (and aim to minimize the number of chords instead of the number of pieces), whereas we make no constraints on the boundaries of the pieces.
