Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R d |
| |
| Authors: | S. Smorodinsky J. S. B. Mitchell M. Sharir |
| |
| Affiliation: | (1) School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel shakhar@math.tau.ac.il, sharir@math.tau.ac.il , IL;(2) Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY 11794, USA jsbm@ams.sunysb.edu http://www.ams.sunysb.edu/~jsbm/ , US;(3) Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA , US |
| |
| 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 [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5]. Received September 21, 1998, and in revised form March 14, 1999. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
