Μέθοδοι κατασκευής κυρτών περιβλημάτων και εφαρμογές

Abstract

Η παρούσα εργασία εξετάζει μια σειρά από αλγόριθμους, οι οποίοι χρησιμοποιούνται για την κατασκευή κυρτών περιβλημάτων στις δύο και τρεις διαστάσεις και αναλύει διάφορες εφαρμογές τους. Στο πρώτο κεφάλαιο της εργασίας θα παρουσιαστούν οι αλγόριθμοι Graham, Jarvis, Chan και οι χρόνοι πολυπλοκότητας που έχουν για την δημιουργία κυρτών περιβλημάτων στις δυο διαστάσεις. Στο δεύτερο κεφάλαιο θα εξετάσουμε την κατασκευή κυρτών περιβλημάτων στις τρεις διαστάσεις και στο τρίτο θα εξετάσουμε τα διαγράμματα Voronoi - Delaunay και τις εφαρμογές αυτών.