Uniformly distributed distances - A geometric application of Janson's inequality

János Pach; Joel Spencer

doi:10.1007/s004930050048

Uniformly distributed distances - A geometric application of Janson's inequality

János Pach, Joel Spencer

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

Abstract

Let d₁ ≤ d₂ ≤ . . . ≤ d_(n2) denote the distances determined by n points in the plane. It is shown that min Σ_i(d_i+1-d_i)²=O(n ^-6/7), where the minimum is taken over all point sets with minimal distance d₁ ≥ 1. This bound is asymptotically tight.

Original language	English (US)
Pages (from-to)	111-124
Number of pages	14
Journal	Combinatorica
Volume	19
Issue number	1
DOIs	https://doi.org/10.1007/s004930050048
State	Published - 1999

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s004930050048

Cite this

@article{2535a10acd744bf0af47797e095f99c2,

title = "Uniformly distributed distances - A geometric application of Janson's inequality",

abstract = "Let d1 ≤ d2 ≤ . . . ≤ d(n2) denote the distances determined by n points in the plane. It is shown that min Σi(di+1-di)2=O(n -6/7), where the minimum is taken over all point sets with minimal distance d1 ≥ 1. This bound is asymptotically tight.",

author = "J{\'a}nos Pach and Joel Spencer",

note = "Funding Information: Mathematics Subject Classi cation (1991): 52C10, 05C80 * Supported by NSF grant CCR-97-32101, PSC-CUNY Research Award 667339 and OTKA-T-020914. This paper was partly written while the rst named author was visiting MSRI Berkeley, as part of the Convex Geometry program.",

year = "1999",

doi = "10.1007/s004930050048",

language = "English (US)",

volume = "19",

pages = "111--124",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Uniformly distributed distances - A geometric application of Janson's inequality

AU - Pach, János

AU - Spencer, Joel

N1 - Funding Information: Mathematics Subject Classi cation (1991): 52C10, 05C80 * Supported by NSF grant CCR-97-32101, PSC-CUNY Research Award 667339 and OTKA-T-020914. This paper was partly written while the rst named author was visiting MSRI Berkeley, as part of the Convex Geometry program.

PY - 1999

Y1 - 1999

N2 - Let d1 ≤ d2 ≤ . . . ≤ d(n2) denote the distances determined by n points in the plane. It is shown that min Σi(di+1-di)2=O(n -6/7), where the minimum is taken over all point sets with minimal distance d1 ≥ 1. This bound is asymptotically tight.

AB - Let d1 ≤ d2 ≤ . . . ≤ d(n2) denote the distances determined by n points in the plane. It is shown that min Σi(di+1-di)2=O(n -6/7), where the minimum is taken over all point sets with minimal distance d1 ≥ 1. This bound is asymptotically tight.

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

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

U2 - 10.1007/s004930050048

DO - 10.1007/s004930050048

M3 - Article

AN - SCOPUS:0040707342

SN - 0209-9683

VL - 19

SP - 111

EP - 124

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Uniformly distributed distances - A geometric application of Janson's inequality

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this