Cutting disjoint disks by straight lines

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

Research output: Contribution to journalArticle

23 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 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.

Original languageEnglish (US)
Pages (from-to)239-243
Number of pages5
JournalDiscrete & Computational Geometry
Volume4
Issue number1
DOIs
StatePublished - Dec 1 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Cutting disjoint disks by straight lines'. Together they form a unique fingerprint.

  • Cite this