National and Kapodistrian University of Athens
Υπολογιστική γεωμετρία για καμπύλα αντικείμενα: διαγράμματα Voronoi στο επίπεδο
Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Tzoumas, Georgios
- Τζούμας, Γεώργιος
Subjects
dc:subject × 18- Γράφος Delaunay
- Διαγράμματα voronoi
- Ακριβής υπολογισμός
- Παραμετρική καμπύλη
- Υλοποίηση CGAL
- Γεωμετρικό κατηγόρημα
- Συμβολικοί-αριθμητικοί υπολογισμοί
- Delaunay graph
- VORONOI DIAGRAM
- Exact computation
- Parametric curve
- CGAL implementation
- Geometric predicate
- Symbolic-numeric computation
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/23969