Delaunay τριγωνοποιηση και πλεγματοποιηση

Abstract

Delaunay τριγωνοποιηση και πλεγματοποιηση

Η ανάλυση πεδίων στο Rd, συνήθως, γίνεται με ανάλυση σε μικρότερα κομμάτιατα οποία θέλουμε να είναι κανονικά. Από την εμπειρία στις διαστάσεις 2 και 3,έχουμε ότι τα κομμάτια αυτά είναι πρέπει να είναι τρίγωνα ή τετράεδρα]. ́Ετσιαπαιτούμε και στις άλλες διαστάσεις να έχουμε τα ανάλογα στοιχεία (simplices).Επίσης, θέλουμε η τομή αυτών των στοιχείων να είναι κανονική, δηλαδή να είναιμια ολόκληρη όψη (σημείο, ακμή, τρίγωνο και τα ανάλογά τους).Από την άλλη δενθέλουμε αυτά τα στοιχεία να είναι πολύ ακανόνιστα. Για παράδειγμα, για τα τρίγωναθέλουμε να είναι όσο πιο κοντά γίνεται στα ισόπλευρα τρίγωνα. Αυτό σημαίνει ότιτα τρίγωνα δεν θα έχουν πολύ μεγάλες (ή πολύ μικρές) γωνίες. Αυτήν ακριβώς τηνιδιότητα κωδικοποιούν οι τριγωνοποιήσεις Delaunay. Αυτές οι τριγωνοποιήσειςείναι και ο καλύτερος τρόπος για να ‘δώσουμε’ το πεδίο στον Ευκλείδειο χώρο καινα χρησιμοποιήσουμε αλγοριθμικά τις ιδιότητές τους.Το πρόβλημα λοιπόν είναι η κατασκευή Delaunay τριγωνοποιήσεων. Αυτό τοδίνουμε σε δυο περιπτώσεις. Η πρώτη είναι η τριγωνοποίηση της κυρτής θήκης πε-περασμένου αριθμού στοιχείων, απαιτώντας ότι τα δεδομένα σημεία είναι κορυφέςτης τριγωνοποίησης. Η δεύτερη περίπτωση είναι η κατασκευή πλέγματος, δηλα-δή τριγωνοποίησης πεδίου στον Ευκλείδειο χώρο, χωρίς κανέναν περιορισμό στιςκορυφές. Αλγοριθμικά, αυτά είναι τα αργά (bottlenecks) σημεία του αλγορίθμουεπίλυσης διαφορικών εξισώσεων με την μέθοδο των πεπερασμένων σττοιχείων.Σ ́ αυτήν την εργασία παρουσιάζουμε τους βασικούς ορισμούς και ιδιότητες τωντριγωνοποιήσεων Delaunay. Επίσης, περιγράφουμε τους βασικούς αλγορίθμουςκατασκευής των τριγωνοποιήσεων και επίσης πως να προσθέσουμε περισσότερεςκορυφές και να κατασκευάσουμε πλέγματα γενικών πεδίων.