Το Quickhull είναι μια μέθοδος υπολογισμού του κυρτού περιβλήματος ενός πεπερασμένου συνόλου σημείων σε ν-διάστατο χώρο. Χρησιμοποιεί μια προσέγγιση διαίρει και βασίλευε παρόμοια με αυτή του quicksort, από την οποία προέρχεται το όνομά του. Η χειρότερη χρονική πολυπλοκότητά του για δισδιάστατο και τρισδιάστατο χώρο είναι \( O(n^{2}) \), αλλά όταν η ακρίβεια εισόδου περιορίζεται σε \( O(\log n) \) bit , η χειρότερη χρονική πολυπλοκότητά του εικάζεται ότι είναι \( {\displaystyle O(n\log r)} \), όπου n n είναι ο αριθμός των σημείων εισόδου και r είναι ο αριθμός των επεξεργασμένων σημείων (έως n ) .[1]
Το N-διάστατο Quickhull επινοήθηκε το 1996 από τους C. Bradford Barber, David P. Dobkin και Hannu Huhdanpaa.[1] Ήταν μια επέκταση του επίπεδου αλγορίθμου Quickhull του Jonathan Scott Greenfield το 1990, αν και οι συγγραφείς του 1996 δεν γνώριζαν τις μεθόδους του.[2] Αντίθετα, οι Barber et al. περιγράψτε το ως μια ντετερμινιστική παραλλαγή του αλγορίθμου των Clarkson και Shor του 1989.[1]
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
