ISSN:
1436-5057
Keywords:
Primary 60E15
;
Secondary
;
Secondary 68C25
;
60D05
;
Moment inequalities
;
computational geometry
;
convex hull
;
maximal vector
;
divide and conquer
;
average complexity
;
analysis of algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung X 1,...,X n seien unabhängige und gleichartig verteilte Zufallsvektoren imR d , ferner seiA n =A(X 1,...,X n ) eine Teilmenge von {X 1,...,X n }, die invariant ist gegenüber einer Permutation der Daten und die die Inklusionseigenschaft (X 1 ∈A n ⇒X 1 ∈A i füri≤n) besitzt. Beispielsweise erfüllen die konvexe Hülle, die Menge der Maximal-Vektoren, die Menge der isolierten Punkte und andere Strukturen diese Bedingungen. SeiN n die Kardinalzahl vonA n . Wir zeigen, daß es für jedesp≥1 eine universelle KonstanteC p gibt, so daßE(N n p )≤C p max (1,E p ) gilt, mit . Dies ist das Gegenstück zur unteren Schranke in Jensen für dasp-te Moment: E(Nn/p)≥Ep(Nn). Die Ungleichung wird zur Analyse der erwarteten Laufzeit von Algorithmen für geometrische Berechnungen verwendet. Ferner werden notwendige und hinreichende Bedingungen bezüglich (E(N n ) angegeben, damit ein lineares Laufzeitverhalten bei Divide-and-Conquer-Methoden zur Berechnung vonA n zu erwarten ist.
Notes:
Abstract LetX 1,...,X n be independent identically distributedR d -valued random vectors, and letA n =A(X 1,...,X n ) be a subset of {X 1,...,X n }, invariant under permutations of the data, and possessing the inclusion property (X 1 ∈A n impliesX 1 ∈A i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these conditions. LetN n be the cardinality ofA n . We show that for allp≥1, there exists a universal constantC p 〉0 such thatE(N n p )≤C p max (1,E p ) where . This complements Jensen's lower bound for thep-th moment:E(N n p )≥E p (N n ). The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N n ) for linear expected time behaviour of divide-and-conquer methods for findingA n .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02280782
Permalink
