Two Applications of Point Matching
Two Applications of Point Matching
复制标题
点匹配的两种应用
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
G. Rote
中科院分区：
文献类型：
--
作者：
G. Rote
以下两个问题可以通过简化为最小权重二分匹配问题（或相关的网络流问题）来解决：a）泛光灯照明：我们给出n个无限楔形（扇区，聚光灯），当放置在原点时，它们可以覆盖整个平面。它们被分配到n个给定的位置（以任意顺序，但不旋转），使它们仍然覆盖整个平面。(This扩展了Bose等人1997年的结果[4]。B）凸分区：将凸m边形划分为m个凸部分，每个部分包含一条边和给定点集中的给定数量的点。(Garc a和Tejel 1995 [5]，Aurenhammer 2008 [3]）
The two following problems can be solved by a reduction to a minimum-weight bipartite matching problem (or a related network ow problem): a) Floodlight illumination: We are given n innite wedges (sectors, spotlights) that can cover the whole plane when placed at the origin. They are to be assigned to n given locations (in arbitrary order, but without rotation) such that they still cover the whole plane. (This extends results of Bose et al. [4] from 1997.) b) Convex partition: Partition a convex m-gon into m convex parts, each part containing one of the edges and a given number of points from a given point set. (Garc a and Tejel 1995 [5], Aurenhammer 2008 [3])