Longest convex chains |
| |
Authors: | Gergely Ambrus Imre Bárány |
| |
Institution: | 1. Department of Mathematics, University College London, London WC1E 6BT, England;2. Bolyai Institute, University of Szeged, 6720 Szeged Hungary;3. Rényi Institute of Mathematics, Hungarian Academy of Sciences, 1364 Budapest, Hungary |
| |
Abstract: | Assume Xn is a random sample of n uniform, independent points from a triangle T. The longest convex chain, Y, of Xn is defined naturally (see the next paragraph). The length |Y| of Y is a random variable, denoted by Ln. In this article, we determine the order of magnitude of the expectation of Ln. We show further that Ln is highly concentrated around its mean, and that the longest convex chains have a limit shape. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 |
| |
Keywords: | random points convex chains concentration limit shape |
|
|