Sharp bounds on geometric permutations of pairwise disjoint balls in Rd

Shakhar Smorodinsky; Joseph S.B. Mitchell; Micha Sharir

doi:10.1145/304893.304994

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

Shakhar Smorodinsky
, Joseph S.B. Mitchell
, Micha Sharir

Applied Mathematics and Statistics

Tel Aviv University

Research output: Contribution to conference › Paper › peer-review

1 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 R^d, is Θ(n^d-1). This improves substantially the upper bound of O(n^2d-2) known for general convex sets. We show that the maximum number of geometric permutations of a sufficiently large collection of pair-wise disjoint unit discs in the plane is 2, improving the previous upper bound of 3 given in [5].

Original language	English
Pages	400-406
Number of pages	7
DOIs	https://doi.org/10.1145/304893.304994
State	Published - 1999
Event	Proceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA Duration: Jun 13 1999 → Jun 16 1999

Conference

Conference	Proceedings of the 1999 15th Annual Symposium on Computational Geometry
City	Miami Beach, FL, USA
Period	06/13/99 → 06/16/99

Access to Document

10.1145/304893.304994

Cite this

@conference{d026363add5a4e668a83756396eaeef7,

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

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

author = "Shakhar Smorodinsky and Mitchell, \{Joseph S.B.\} and Micha Sharir",

year = "1999",

doi = "10.1145/304893.304994",

language = "English",

pages = "400--406",

note = "Proceedings of the 1999 15th Annual Symposium on Computational Geometry ; Conference date: 13-06-1999 Through 16-06-1999",

}

TY - CONF

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

AU - Smorodinsky, Shakhar

AU - Mitchell, Joseph S.B.

AU - Sharir, Micha

PY - 1999

Y1 - 1999

N2 - We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in Rd, is Θ(nd-1). This improves substantially the upper bound of O(n2d-2) known for general convex sets. We show that the maximum number of geometric permutations of a sufficiently large collection of pair-wise disjoint unit discs in the plane is 2, improving the previous upper bound of 3 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 Rd, is Θ(nd-1). This improves substantially the upper bound of O(n2d-2) known for general convex sets. We show that the maximum number of geometric permutations of a sufficiently large collection of pair-wise disjoint unit discs in the plane is 2, improving the previous upper bound of 3 given in [5].

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

U2 - 10.1145/304893.304994

DO - 10.1145/304893.304994

M3 - Paper

AN - SCOPUS:0032680553

SP - 400

EP - 406

T2 - Proceedings of the 1999 15th Annual Symposium on Computational Geometry

Y2 - 13 June 1999 through 16 June 1999

ER -

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

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this