ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Given a setA inR 2 and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane. We prove that, for any collectionF ofn disjoint disks inR 2, there is a lineL that separates a disk inF from a subcollection ofF with at least ⌌(n−7)/4⌍ disks. We produce configurationsH n andG n , withn and 2n disks, respectively, such that no pair of disks inH n can be simultaneously separated from any set with more than one disk ofH n , and no disk inG n can be separated from any subset ofG n with more thann disks. We also present a setJ m with 3m line segments inR 2, such that no segment inJ m can be separated from a subset ofJ m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least ⌌n/3⌍+1 elements ofF.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187835
Permalink
