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:
Cambridge University Press (CUP), 1988
Erschienen in:
Journal of Applied Probability, 25 (1988) 4, Seite 688-699
Sprache:
Englisch
DOI:
10.2307/3214289
ISSN:
0021-9002;
1475-6072
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.