| Two Applications of Point Matching (2009) | |||||||||||||
Abstract | |||||||||||||
| 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). @InProceedings{rote:DSP:2009:2029, author = {G{"u}nter Rote}, title = {Two Applications of Point Matching}, booktitle = {Computational Geometry}, year = {2009}, editor = {Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud}, number = {09111}, series = {Dagstuhl Seminar Proceedings}, ISSN = {1862-4405}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2029}, annote = {Keywords: Bipartite matching, least-squares} } | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||