Υπολογιστική γεωμετρία για καμπύλα αντικείμενα: διαγράμματα Voronoi στο επίπεδο

Abstract

In this dissertation we examine the problem of computing exactly the Delaunay graph (and the dual Voronoi diagram) of a set of, possibly intersecting, smooth convex pseudo-circles in the Euclidean plane, given in parametric form. Pseudo-circles are closed curves, every pair of which has at most two intersection points. The Delaunay graph is constructed incrementally. We propose robust and efficient algorithms for all required predicates, analyzing their algebraic complexity, under the exact computation paradigm. We focus on InCircle, which is the hardest predicate, and express it by a simple sparse 5x5 polynomial system, which allows for an efficient implementation by means of successive Sylvester resultants and a factorization lemma. To speed up the algebraic computations, we study several geometric properties of the problem and provide a subdivision based algorithm that exhibits quadratic convergence, allowing us to answer the predicate in real-time for the non-degenerate cases. Finally, we present a CGAL-based C++ implementation for the case of ellipses, which is, to the best of our knowledge, the first exact implementation in non-linear computational geometry that deals with algebraic numbers of degree 184. Our code spends 98 sec to construct the Delaunay graph of a set of 128 non-intersecting ellipses, when no degeneracies occur. We show that our specialized methods for ellipses are faster than generic symbolic-numeric software. Moreover, our implementation is faster than the CGAL segment Delaunay graph, when ellipses are approximated by k-gons for k > 15, and then the Voronoi diagram of points, when each ellipse is approximated by more than 240 points.

Στη διατριβή αυτή εξετάζουμε το πρόβλημα του ακριβούς υπολογισμού του γράψου Delaunay (και του δυϊκού διαγράμματος Voronoi) ενός συνόλου, ενδεχομένως τεμνόμενων, κυρτών ομαλών ψευδοκύκλων του Ευκλείδειου επιπέδου, που δίνονται σε παραμετρική μορφή. Ψευδοκύκλοι ονομάζονται κλειστές καμπύλες, τα ζεύγη των οποίων τέμνονται σε δύο το πολύ σημεία. Ο γράφος Delaunay κατασκευάζεται αυξητικά. Προτείνουμε αποτελεσματικούς αλγορίθμους για όλα τα απαιτούμενα κατηγορήματα, αναλύοντας την αλγεβρική τους πολυπλοκότητα, υπό το πρότυπο της ακριβούς αριθμητικής. Εστιάζουμε στο InCircle, το οποίο αποτελεί το δυσκολότερο κατηγόρημα, εκφράζοντάς το με ένα απλό αραιό πολυωνυμικό σύστημα 5x5, το οποίο θα μας οδηγήσει σε μία αποτελεσματική υλοποίηση μέσω διαδοχικών απαλοιφουσών Sylvester και ενός λήμματος παραγοντοποίησης. Για να επιταχύνουμε τους αλγεβρικούς υπολογισμούς, μελετάμε ορισμένες γεωμετρικές ιδιότητες του προβλήματος και παρέχουμε έναν αλγόριθμο υποδιαίρεσης τετραγωνικής σύγκλισης, ο οποίος μας επιτρέπει να απαντάμε στο κατηγόρημα σε πραγματικό χρόνο, στις μη εκφυλισμένες περιπτώσεις. Τέλος, υλοποιούμε τις παραπάνω τεχνικές για ελλείψεις σε C++, βασιζόμενοι στη βιβλιοθήκη CGAL. Πρόκειται, απ’ όσο γνωρίζουμε, για την πρώτη ακριβή υλοποίηση μη γραμμικής υπολογιστικής γεωμετρίας η οποία χειρίζεται αλγεβρικούς αριθμούς βαθμού 184. Για την κατασκευή του γράψου Delaunay ενός συνόλου 128 μη τεμνόμενων ελλείψεων, ο κώδικάς μας χρειάζεται 98 sec, όταν δεν προκύπτουν εκφυλισμένες περιπτώσεις. Δείχνουμε ότι οι εξειδικευμένες μέθοδοι που αναπτύχθηκαν για ελλείψεις είναι γρηγορότερες από γενικό λογισμικό συμβολικών-αριθμητικών υπολογισμών. Επιπλέον, η υλοποίησή μας είναι γρηγορότερη από τον υπολογισμό του γράφου Delaunay ευθυγράμμων τμημάτων της CGAL, όταν οι ελλείψεις προσεγγίζονται με ν-γωνα, με ν > 15, και από το διάγραμμα Voronoi σημείων, όταν κάθε έλλειψη προσεγγίζεται με περισσότερα από 240 σημεία.