caa a22 4500 469075430 CHVBK 20180323132934.0 cr unu---uuuuu 170328e19920201xx s 000 0 eng 10.1007/BF02187835 doi (NATIONALLICENCE)springer-10.1007/BF02187835 Separating convex sets in the plane [Elektronische Daten] [Jurek Czyzowicz, Eduardo Rivera-Campo, Jorge Urrutia, Joseph Zaks] 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. Springer-Verlag New York Inc., 1992 Czyzowicz Jurek Département d'Informatique, Université du Québec à Hull, Hull, Québec, Canada aut Rivera-Campo Eduardo Departamento de Matemáticas, Universidad Autónoma Metropolitana-I, México D.F., México aut Urrutia Jorge Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada aut Zaks Joseph Department of Mathematics, University of Haifa, Haifa, Israel aut Discrete & Computational Geometry Springer New York 7/2(1992-02-01), 189-195 0179-5376 7:2<189 1992 7 454 https://doi.org/10.1007/BF02187835 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187835 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Czyzowicz Jurek Département d'Informatique, Université du Québec à Hull, Hull, Québec, Canada aut NATIONALLICENCE 700 1- Rivera-Campo Eduardo Departamento de Matemáticas, Universidad Autónoma Metropolitana-I, México D.F., México aut NATIONALLICENCE 700 1- Urrutia Jorge Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada aut NATIONALLICENCE 700 1- Zaks Joseph Department of Mathematics, University of Haifa, Haifa, Israel aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/2(1992-02-01), 189-195 0179-5376 7:2<189 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer