2022/01/26 by Rote, Günter
#Bipartite matching #least-squares
paper · doi:10.4230/dagsemproc.09111.6
The two following problems can be solved by a reduction to a minimum-weight bipartite matching problem (or a related network flow problem): a) Floodlight illumination: We are given n infinite 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. 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. (Garcia and Tejel 1995, Aurenhammer 2008)