Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
On the Convex Hull of Random Points in a Polytope
Beteiligte:
Dwyer, Rex A.
Erschienen:
Applied Probability Trust, 1988
Erschienen in:
Journal of Applied Probability, 25 (1988) 4, Seite 688-699
Sprache:
Englisch
ISSN:
0021-9002
Entstehung:
Anmerkungen:
Beschreibung:
The convex hull of n points drawn independently from a uniform distribution on the interior of a d-dimensional polytope is investigated. It is shown that the expected number of vertices is O(logd-1n) for any polytope, the expected number of vertices is Ω(logd-1n) for any simple polytope, and the expected number of facets is O(logd-1n) for any simple polytope. An algorithm is presented for constructing the convex hull of such sets of points in linear average time.