Günter Rote:
Two applications of point matching
In: Abstracts of the 25th European Workshop on Computational Geometry
(EuroCG'09), Brussels, March 2009, pp. 187–189.
Abstract
The two following problems can be solved by a reduction to a minimum-weight
bipartite matching 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. (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 inside the
polygon.
Note on priority
Problem (a) has already been solved in the same way by
V. Galperin and G. Galperin, Osveshchenije ploskosti prozhektorami (Illuminating
a plane with spotlights). Kvant 11, no. 11 (1981), 28-30 (in Russian).
Last update: July 26, 2009.