A Tight Bound on the Number of Geometric Permutations of Convex Fat Objects in R
d |
| |
| Authors: | M J Katz K R Varadarajan |
| |
| Institution: | (1) Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel matya@cs.bgu.ac.il, IL;(2) Department of Computer Science, University of Iowa, Iowa City, IA 52242, USA kvaradar@cs.uiowa.edu, US |
| |
| Abstract: | We show that the maximum number of geometric permutations of a set of n pairwise-disjoint convex and fat objects in R
d
is O(n
d-1
) . This generalizes the bound of Θ (n
d-1
) obtained by Smorodinsky et al. 5] on the number of geometric permutations of n pairwise-disjoint balls.
Received August 22, 2000, and in revised form February 6, 2001. Online publication October 12, 2001. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
