## 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. 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.