Separating Pairs of Points by Standard Boxes

Noga Alon, Z. Füredi, M. Katchalski

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Let A be a set of distinct points in ℝd. A 2-subset {a, b} of A is called separated if there exists a closed box with sides parallel to the axes, containing a and b but no other points of A. Let s(A) denote the number of separated 2-sets of A and put f(n, d) = max {s(A): A ⊂ ℝd, |A| = n}. We show that f(n, 2) = [n2/4] + n − 2 for all n≥2 and that for each fixed dimension d f(n,d)=(1−1/2 2 d−1−1)⋅n2/2+o(n2).

Original languageEnglish (US)
Pages (from-to)205-210
Number of pages6
JournalEuropean Journal of Combinatorics
Issue number3
StatePublished - 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Separating Pairs of Points by Standard Boxes'. Together they form a unique fingerprint.

Cite this