Cutting disjoint disks by straight lines

N. Alon; M. Katchalski; W. R. Pulleyblank

doi:10.1007/BF02187724

Cutting disjoint disks by straight lines

N. Alon, M. Katchalski, W. R. Pulleyblank

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

Abstract

For k>0 let f(k) denote the minimum integer f such that, for any family of k pairwise disjoint congruent disks in the plane, there is a direction α such that any line having direction α intersects at most f of the disks. We determine the exact asymptotic behavior of f(k) by proving that there are two positive constants d₁, d₂ such that d₁√k √log k≤f(k)≤d₂√k √log k. This result has been motivated by problems dealing with the separation of convex sets by straight lines.

Original language	English (US)
Pages (from-to)	239-243
Number of pages	5
Journal	Discrete & Computational Geometry
Volume	4
Issue number	1
DOIs	https://doi.org/10.1007/BF02187724
State	Published - Dec 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/BF02187724

Cite this

@article{894c1d417ba343e8bb6371e2b350a108,

title = "Cutting disjoint disks by straight lines",

abstract = "For k>0 let f(k) denote the minimum integer f such that, for any family of k pairwise disjoint congruent disks in the plane, there is a direction α such that any line having direction α intersects at most f of the disks. We determine the exact asymptotic behavior of f(k) by proving that there are two positive constants d1, d2 such that d1√k √log k≤f(k)≤d2√k √log k. This result has been motivated by problems dealing with the separation of convex sets by straight lines.",

author = "N. Alon and M. Katchalski and Pulleyblank, {W. R.}",

year = "1989",

month = dec,

doi = "10.1007/BF02187724",

language = "English (US)",

volume = "4",

pages = "239--243",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Cutting disjoint disks by straight lines

AU - Alon, N.

AU - Katchalski, M.

AU - Pulleyblank, W. R.

PY - 1989/12

Y1 - 1989/12

N2 - For k>0 let f(k) denote the minimum integer f such that, for any family of k pairwise disjoint congruent disks in the plane, there is a direction α such that any line having direction α intersects at most f of the disks. We determine the exact asymptotic behavior of f(k) by proving that there are two positive constants d1, d2 such that d1√k √log k≤f(k)≤d2√k √log k. This result has been motivated by problems dealing with the separation of convex sets by straight lines.

AB - For k>0 let f(k) denote the minimum integer f such that, for any family of k pairwise disjoint congruent disks in the plane, there is a direction α such that any line having direction α intersects at most f of the disks. We determine the exact asymptotic behavior of f(k) by proving that there are two positive constants d1, d2 such that d1√k √log k≤f(k)≤d2√k √log k. This result has been motivated by problems dealing with the separation of convex sets by straight lines.

UR - http://www.scopus.com/inward/record.url?scp=0347540121&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347540121&partnerID=8YFLogxK

U2 - 10.1007/BF02187724

DO - 10.1007/BF02187724

M3 - Article

AN - SCOPUS:0347540121

SN - 0179-5376

VL - 4

SP - 239

EP - 243

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

Cutting disjoint disks by straight lines

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this