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)
BibTeX - Entry
@InProceedings{rote:DagSemProc.09111.6,
author = {Rote, G\"{u}nter},
title = {{Two Applications of Point Matching}},
booktitle = {Computational Geometry},
pages = {1--3},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2009},
volume = {9111},
editor = {Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2009/2029},
URN = {urn:nbn:de:0030-drops-20292},
doi = {10.4230/DagSemProc.09111.6},
annote = {Keywords: Bipartite matching, least-squares}
}
|
Keywords: |
|
Bipartite matching, least-squares |
|
Collection: |
|
09111 - Computational Geometry |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
24.06.2009 |
Creative Commons Attribution 4.0 International license (CC BY 4.0)