In:
Advances in Applied Probability, Cambridge University Press (CUP), Vol. 25, No. 02 ( 1993-06), p. 373-394
Abstract:
While the convex hull of n d -dimensional balls is not a polytope, it does have an underlying combinatorial structure similar to that of a polytope. In the worst case, its combinatorial complexity can be of order Ω( n [ d /2] ). The thrust of this work is to show that its complexity is typically much smaller, and that it can therefore be constructed more quickly on average than in the worst case. To this end, four models of the random d -ball are developed, and the expected combinatorial complexity of the convex hull of n independent random d -balls is investigated for each. As n grows without bound, these expectations are O (1), O ( n ( d –1)/( d +4) ), O (1) (for d = 2 only), and O ( n ( d– 1)/( d+ 3) ).
Type of Medium:
Online Resource
ISSN:
0001-8678
,
1475-6064
DOI:
10.1017/S0001867800025404
Language:
English
Publisher:
Cambridge University Press (CUP)
Publication Date:
1993
detail.hit.zdb_id:
1474602-5
detail.hit.zdb_id:
160005-9
Permalink
