QuickHull
Sign in to saveQuickhull is a method of computing the convex hull of a finite set of points in n-dimensional space. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its worst case time complexity for 2-dimensional and 3-dimensional space is O(n^2), but when the input precision is restricted to O(\log n) bits, its worst case time complexity is conjectured to be O(n \log r), where n is the number of input points and r is the number of processed points (up to n).
Wikidata facts
- Instance of
- convex hull algorithm
- Based on
- quicksort
Show 3 more facts
- Commons category
- QuickHull
- point in time
- 1995-00-00
- publication date
- 1995-00-00
Sources (1)
via Wikidata · CC0
Article · Deutsch
QuickHull ist ein Algorithmus zur Berechnung der konvexen Hülle einer beliebigen endlichen Menge von Punkten im zwei- oder dreidimensionalen Raum. Die konvexe Hülle einer Menge von Punkten wird beschrieben durch einen geschlossenen Polygonzug, der die Verbindung aller Extremalpunkte der Menge darstellt, und somit alle Punkte der Menge einschließt. Eine häufig verwendete intuitive Erklärung dieser Hülle ist ein Gummiband, welches sich um die Punktemenge spannt. Dieses bildet, wenn es straff auf allen äußeren Punkten aufliegt, die konvexe Hülle der Punktemenge.
Abstract from DBpedia / Wikipedia · CC BY-SA