Cutting glass

Authors
Citation
J. Pach et G. Tardos, Cutting glass, DISC COM G, 24(2-3), 2000, pp. 481-495
Citations number
13
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE & COMPUTATIONAL GEOMETRY
ISSN journal
01795376 → ACNP
Volume
24
Issue
2-3
Year of publication
2000
Pages
481 - 495
Database
ISI
SICI code
0179-5376(200009/10)24:2-3<481:CG>2.0.ZU;2-T
Abstract
Urrutia asked the following question: Given a family of pairwise disjoint c ompact convex sets on a sheet of glass, is it true that one can always sepa rate from one another a constant fraction of them using edge-to-edge straig ht-line cuts? We answer this question in the negative, and establish some l ower and upper bounds for the number of separable sets. We also consider th e special cases when the family consists of intervals, axis-parallel rectan gles, "fat" sets, or "fat" sets with bounded size.