Separating convex sets in the plane |
| |
Authors: | Jurek Czyzowicz Eduardo Rivera-Campo Jorge Urrutia Joseph Zaks |
| |
Institution: | (1) Département d'Informatique, Université du Québec à Hull, Hull, Québec, Canada;(2) Departamento de Matemáticas, Universidad Autónoma Metropolitana-I, México D.F., México;(3) Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada;(4) Department of Mathematics, University of Haifa, Haifa, Israel |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|