|
Identifier |
000421793 |
|
h |
Title |
Predicates of the 3D apollonius diagram |
Alternative Title |
Κατηγορήματα για το τρισδιάστατο Απολλώνιο Διάγραμμα |
Author
|
Καμαριανάκης, Εμμανουήλ
|
Thesis advisor
|
Καραβελάς, Μενέλαος
|
Reviewer
|
Φειδάς, Αθανάσιος
Εμίρης, Ιωάννης
Λάμπρου, Μιχαήλ
Παλιός, Λεωνίδας
Πλεξουσάκης, Μιχαήλ
Τζανάκης, Νικόλαος
|
Abstract |
In this thesis we study one of the fundamental predicates required for the construction of
the 3D Apollonius diagram (also known as the 3D Additively Weighted Voronoi diagram),
namely the EdgeConflict predicate: given five sites Si , Sj , Sk , Sl , Sm that define an edge
ei jklm in the 3D Apollonius diagram, and a sixth query site Sq, the predicate determines the
portion of ei jklm that will disappear in the Apollonius diagram of the six sites due to the
insertion of Sq.
Our focus is on the algorithmic analysis of the predicate with the aim to minimize its
algebraic degree. We decompose the main predicate into sub-predicates, which are then
evaluated with the aid of additional primitive operations. We show that the maximum
algebraic degree required to answer any of the sub-predicates and primitives, and, thus, our
main predicate is 10 in non-degenerate configurations when the trisector is of Hausdorff
dimension 1. We also prove that all subpredicates developed can be evaluated using 10 or
8-degree demanding operations for degenerate input for these trisector types, depending on
whether they require the evaluation of an intermediate InSphere predicate or not.
Among the tools we use is the 3D inversion transformation and the so-called qualitative
symbolic perturbation scheme. Most of our analysis is carried out in the inverted space,
which is where our geometric observations and analysis is captured in algebraic terms.
|
Language |
English, Greek |
Subject |
Euclidean Apollonius diagram |
|
Αλγεβρικοί υπολογισμοί |
|
Ευκλείδειο απολλώνιο διάγραμμα |
|
Υπολογιστική γεωμετρία |
Issue date |
2019-03-22 |
Collection
|
School/Department--School of Sciences and Engineering--Department of Mathematics and Applied Mathematics--Doctoral theses
|
|
Type of Work--Doctoral theses
|
Permanent Link |
https://elocus.lib.uoc.gr//dlib/9/0/a/metadata-dlib-1553770237-777686-19155.tkl
|
Views |
410 |