נתן רובין

אקדמי בכיר

Improved bounds for geometric permutations

Natan Rubin, Haim Kaplan, Micha Sharir

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in double-struck Rd, for d ≥ 3, is O(n2d-3 log n), improving Wenger's 20 years old bound of O(n2d-2).

שפת פרסום אנגלית
דפים 355-364
סטטוס פרסום פורסם - 01.01.2010
מספר מאמר 5671203

Keywords

Arrangements
Convex sets
Geometric permutations
Line transversals

ASJC Scopus subject areas

General Computer Science
גישה למסמך
10.1109/FOCS.2010.41
קבצים וקישורים אחרים
Link to publication in Scopus