[Mittagsseminar TI] Mittagsseminar Dienstag 22.4. Verteidigung meiner Masterarbeit Ying Wei "Curves Approximation by Bezier-Splines"

[Günter Rote <rote@inf.fu-berlin.de>]

Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit dem
Titel "Curves Approximation by Bezier-Splines, Tracing Pixel-Wise
Generated Voronoi Diagrams"ein.

Der Betreuer ist Prof. Dr. Günter Rote.
Der Zweitgutachter ist Prof. Dr. Elfriede Fehr.

Der Vortrag findet am Dienstag, den 22.04.2014 um 12:00 (s.t.) im Raum 055
statt.

Mit freundlichen Grüßen

Ying Wei



Abstract:

Computational geometry devotes itself to exploring and studying efficient
algorithms of geometry. The common methods of constructing Voronoi
diagrams are the applications of the Voronoi-Delaunay duality and the
Fortune's algorithm. This thesis introduces an applicable procedure to
approximate the pixel-wise generated Voronoi diagrams by cubic B\'ezier
splines. This approach can be utilized not only for ordinary Voronoi
diagrams but also for weighted Voronoi diagrams. The points of Voronoi
edges will be computed based on the characteristics of Voronoi diagrams.
We apply a designed Greedy algorithm and cubic Bezier splines to trace the
Voronoi edges.
One of the difficult points is how to deal with the corners of the Voronoi
diagrams. The corners refer to the positions where the edges join and
split. In ordinary Voronoi diagram, the corners are the vertices of
Voronoi. The vertices can be calculated by computing the circumcenters of
triangles of Delaunay triangulation. However, it is not so easy to obtain
the vertices of the weighted Voronoi diagrams. Some points near the
endpoints of edges might not be correctly calculated. Then some unsharp
corners took shape when the endpoints of the edges in the corner are
directly connected. In the work, the positions of joins and splits in the
plane are firstly recognized. Then the junctions in the positions of joins
and splits of edges are handled by binary search. When the join points or
split points are found, we insert them into the corresponding positions of
the related edges.