DocumentCode :
1708337
Title :
Improved Bounds for Geometric Permutations
Author :
Rubin, Natan ; Kaplan, Haim ; Sharir, Micha
Author_Institution :
Tel Aviv Univ., Tel Aviv, Israel
fYear :
2010
Firstpage :
355
Lastpage :
364
Abstract :
We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in Rd, for d ≥ 3, is O(n2d-3 log n), improving Wenger´s 20 years old bound of O(n2d-2).
Keywords :
geometry; set theory; geometric permutation; pairwise disjoint convex set; Complexity theory; Face; Geometry; Indexes; Polynomials; Shape; Upper bound; arrangements; convex sets; geometric permutations; line transversals;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
Conference_Location :
Las Vegas, NV
ISSN :
0272-5428
Print_ISBN :
978-1-4244-8525-3
Type :
conf
DOI :
10.1109/FOCS.2010.41
Filename :
5671203
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=1708337
بازگشت