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.


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.

  pdf file (gzipped)
other papers about this subject

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.