A Constant Bound for Geometric Permutations of Disjoint Unit Balls |
| |
| Authors: | Katchalski Suri Zhou |
| |
| Institution: | (1) Faculty of Mathematics, Technion, Haifa 32000, Israel meirk@techunix.technion.ac.il , IL;(2) Computer Science Department, University of California, Santa Barbara, CA 93106, USA suri@cs.ucsb.edu , US;(3) Compaq Systems Research Center, 130 Lytton Ave, Palo Alto, CA 94301, USA yzhou@pa.dec.com, US |
| |
| Abstract: |
Abstract. We prove that a set of n disjoint unit balls in R
d
admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry.
The constant bound significantly improves upon the Θ (n
d-1
) bound for disjoint balls of unrestricted radii. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
