Sharp bounds on geometric permutations of pairwise disjoint balls in ℝd

S. Smorodinsky; J. S.B. Mitchell; M. Sharir

doi:10.1007/PL00009498

Sharp bounds on geometric permutations of pairwise disjoint balls in ℝ^d

S. Smorodinsky
, J. S.B. Mitchell
, M. Sharir

Applied Mathematics and Statistics

Tel Aviv University
New York University

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

31 Scopus citations

Abstract

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in ℝ^d, is Θ(n^d-1). This improves substantially the upper bound of O(n^2d-2) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5].

Original language	English
Pages (from-to)	247-259
Number of pages	13
Journal	Discrete and Computational Geometry
Volume	23
Issue number	2
DOIs	https://doi.org/10.1007/PL00009498
State	Published - Mar 2000

Access to Document

10.1007/PL00009498

Cite this

@article{68c2d173469a48cd9ff878c5a7aeb28b,

title = "Sharp bounds on geometric permutations of pairwise disjoint balls in ℝd",

abstract = "We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in ℝd, is Θ(nd-1). This improves substantially the upper bound of O(n2d-2) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5].",

author = "S. Smorodinsky and Mitchell, \{J. S.B.\} and M. Sharir",

year = "2000",

month = mar,

doi = "10.1007/PL00009498",

language = "English",

volume = "23",

pages = "247--259",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

number = "2",

}

TY - JOUR

T1 - Sharp bounds on geometric permutations of pairwise disjoint balls in ℝd

AU - Smorodinsky, S.

AU - Mitchell, J. S.B.

AU - Sharir, M.

PY - 2000/3

Y1 - 2000/3

N2 - We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in ℝd, is Θ(nd-1). This improves substantially the upper bound of O(n2d-2) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5].

AB - We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in ℝd, is Θ(nd-1). This improves substantially the upper bound of O(n2d-2) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5].

UR - https://www.scopus.com/pages/publications/0038831314

U2 - 10.1007/PL00009498

DO - 10.1007/PL00009498

M3 - Article

AN - SCOPUS:0038831314

SN - 0179-5376

VL - 23

SP - 247

EP - 259

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

Sharp bounds on geometric permutations of pairwise disjoint balls in ℝ^d

Abstract

Access to Document

Other files and links

Fingerprint

Cite this