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.

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

  pdf file (gzipped)
other papers about this subject
Last update: July 26, 2009.