DagSemProc.09111.6.pdf
- Filesize: 164 kB
- 3 pages
Document
Two Applications of Point Matching
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9111
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2009-06-24
Cite As Get BibTex
Günter Rote. Two Applications of Point Matching. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09111.6
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)
Subject Classification
Keywords
- Bipartite matching
- least-squares
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads