Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23969

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Tzoumas, Georgios; Τζούμας, Γεώργιος. Υπολογιστική γεωμετρία για καμπύλα αντικείμενα: διαγράμματα Voronoi στο επίπεδο. National and Kapodistrian University of Athens, 2009. http://hdl.handle.net/10442/hedi/23969