Improved Bounds for Geometric Permutations

被引：1
|
作者：
Rubin, Natan [1 ]
Kaplan, Haim [1 ]
Sharir, Micha [1 ]
机构：
[1] Tel Aviv Univ, IL-69978 Tel Aviv, Israel
来源：
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | 2010年
关键词：
geometric permutations; line transversals; convex sets; arrangements; CONVEX-SETS; LINE TRANSVERSALS; R-D; NUMBER; BALLS;
D O I：
10.1109/FOCS.2010.41
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in R(d), for d >= 3, is O(n(2d-3) log n), improving Wenger's 20 years old bound of O(n(2d-2)).
引用
收藏
页码：355 / 364
页数：10
相关论文
共 50 条
  • [1] IMPROVED BOUNDS FOR GEOMETRIC PERMUTATIONS
    Rubin, Natan
    Kaplan, Haim
    Sharir, Micha
    SIAM JOURNAL ON COMPUTING, 2012, 41 (02) : 367 - 390
  • [2] Sharp bounds on geometric permutations of pairwise disjoint balls in Rd
    Smorodinsky, Shakhar
    Mitchell, Joseph S.B.
    Sharir, Micha
    Proceedings of the Annual Symposium on Computational Geometry, 1999, : 400 - 406
  • [3] UPPER-BOUNDS ON GEOMETRIC PERMUTATIONS FOR CONVEX-SETS
    WENGER, R
    DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (01) : 27 - 33
  • [4] Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in Rd
    S. Smorodinsky
    J. S. B. Mitchell
    M. Sharir
    Discrete & Computational Geometry, 2000, 23 : 247 - 259
  • [5] Sharp bounds on geometric permutations of pairwise disjoint bails in Rd
    Smorodinsky, S
    Mitchell, JSB
    Sharir, M
    DISCRETE & COMPUTATIONAL GEOMETRY, 2000, 23 (02) : 247 - 259
  • [6] Geometric Permutations
    Boehm, Johannes
    RESULTS IN MATHEMATICS, 2011, 59 (3-4) : 327 - 347
  • [7] Geometric Permutations
    Johannes Böhm
    Results in Mathematics, 2011, 59 : 327 - 347
  • [8] Improved Lower Bounds on the Size of Balls Over Permutations With the Infinity Metric
    Schwartz, Moshe
    Vontobel, Pascal O.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (10) : 6227 - 6239
  • [9] GEOMETRIC SETS OF PERMUTATIONS
    CAMERON, PJ
    GEOMETRIAE DEDICATA, 1988, 25 (1-3) : 339 - 351
  • [10] On neighbors in geometric permutations
    Sharir, M
    Smorodinsky, S
    ALGORITHM THEORY - SWAT 2002, 2002, 2368 : 131 - 139
12345