Maximal and minimal balls

✍ Scribed by Rex A. Dwyer

• Book ID: 103962506
• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 802 KB
• Volume: 3
• Category: Article
• ISSN: 0925-7721
• DOI: 10.1016/0925-7721(93)90017-z

✦ Synopsis

Let S be a set of balls in Rd. We call a ball in S maximal if no other ball in S contains it, and minimal if it contains no other ball. The expected number of maximal and minimal balls in a set of n independent and identically distributed random balls is investigated. These quantities are found to be o(n) for any absolutely continuous distribution.

Their behavior is investigated more precisely for three specific distributions.

It is also shown that Bentley, Clarkson, and Levine's move-to-front strategy provides an efficient algorithm for identifying maximal minimal balls. Since only maximal balls lie on the boundary of the convex hull of the set, this provides a good preprocessing step for constructing the convex hull of a set of balls.