ISSN:
1436-5057
Keywords:
Convex hull
;
average complexity
;
geometrical complexity
;
algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir betrachtenn als unabhängig identisch verteilte Zufallsvektoren imR d mit der gemeinsamen Verteilungsdichtef. Die mittlere Konvexität eines Algorithmus zur Bestimmung der konvexen Hülle dieser Punkte seiE (C). Die meisten bekannten Algorithmen genügen für gewisse Klassen von Dichten der BedingungE (C)=0(n). In dieser Mitteilung zeigen wirE (C)=0(n) für Algorithmen, die im Vorlauf einen „Wegwerf-Schritt” benützen, wennf auf jedem nicht ausgearteten Rechteck desR 2 beschränkt ist und positiven Abstand von 0 besitzt.
Notes:
Abstract Considern independent identically distributed random vectors fromR d with common densityf, and letE (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfyE (C)=0(n) for certain classes of densities. In this note, we show thatE (C)=0(n) for algorithms that use a “throw-away” pre-processing step whenf is bounded away from 0 and ∞ on any nondegenerate rectangle ofR 2.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02237955
