Piercing Balls Sitting on a Table by a Vertical Line

✍ Scribed by Hiroshi Maehara; Ai Oshiro

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 127 KB
• Volume: 21
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1999.0364

✦ Synopsis

Let F n be a family of disjoint n balls all sitting on a fixed horizontal table T . Let denote a vertical line that meets T . We prove that if meets 2k + 1 balls in F n , then the radius of the smallest ball among the 2k + 1 balls is at most (2 -√ 3) k times the radius of the biggest ball among the 2k + 1 balls. Using this result we prove that for any F n the average number of balls an meets is at most log n + o(1). A similar result for a two-dimensional version is also given together with a lower bound of the least upper bound.