Covering convex sets with non-overlapping polygons
Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping polygons. Discrete Mathematics. 81(2), 153–164.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Robison, Arch;
Shen, Xiao
;
Robison, Arch;
Shen, XiaoAbstract
We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the plane, they may be covered with n non-overlapping convex polygons with a total of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore, we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound on the number of slopes implies a new bound on a recently studied transversal problem.
Publishing Year
Date Published
1990-04-15
Journal Title
Discrete Mathematics
Acknowledgement
The first author acknowledges the support by Amoco Fnd. Fat. Dev. Comput. Sci. l-6-44862. Work on this paper by the second author was supported by a Shell Fellowship in Computer Science. The third author as supported by the office of Naval Research under grant NOOO14-86K-0416.
Volume
81
Issue
2
Page
153 - 164
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Robison A, Shen X. Covering convex sets with non-overlapping polygons. Discrete Mathematics. 1990;81(2):153-164. doi:10.1016/0012-365X(90)90147-A
Edelsbrunner, H., Robison, A., & Shen, X. (1990). Covering convex sets with non-overlapping polygons. Discrete Mathematics. Elsevier. https://doi.org/10.1016/0012-365X(90)90147-A
Edelsbrunner, Herbert, Arch Robison, and Xiao Shen. “Covering Convex Sets with Non-Overlapping Polygons.” Discrete Mathematics. Elsevier, 1990. https://doi.org/10.1016/0012-365X(90)90147-A.
H. Edelsbrunner, A. Robison, and X. Shen, “Covering convex sets with non-overlapping polygons,” Discrete Mathematics, vol. 81, no. 2. Elsevier, pp. 153–164, 1990.
Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping polygons. Discrete Mathematics. 81(2), 153–164.
Edelsbrunner, Herbert, et al. “Covering Convex Sets with Non-Overlapping Polygons.” Discrete Mathematics, vol. 81, no. 2, Elsevier, 1990, pp. 153–64, doi:10.1016/0012-365X(90)90147-A.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar