Predicates of the 3D apollonius diagram

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 Conflict predicate: given five sites S_i, S_j,S_k,S_l,S_m that define an edge e_{ijklm} in the 3D Apollonius diagram, and a sixth query site S_q, the predicate determines the portion of e_{ijklm} that will disappear in the Apollonius diagram of the six sites due to the insertion of $S_q$. 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.

Στην εργασία αυτή μελετάμε ένα από τα κεντρικότερα κατηγορήματα το οποίο απαιτείται για την κατασκευή του 3-Διάστατου Απολλώνιου Διαγράμματος (γνωστό και ως Voronoi διάγραμμα βεβαρυμένων σημείων), το επονομαζόμενο κατηγόρημα \conflict: δεδομένων 5 σφαιρών S_i, S_j,S_k,S_l,S_m τα οποία ορίζουν μια ακμή e_{ijklm} στο Απολλώνιο διάγραμμα και μίας έκτης σφαίρας $S_q$, το κατηγόρημα αποφαίνεται ποιο υποσύνολο της $\edge{ijklm}$ θα πάψει να υπάρχει ως ακμή στο στο Απολλώνιο διάγραμματων 6 σφαιρών. Το κύριο μέλημά μας είναι η αλγοριθμική ανάλυση του κατηγορήματος αυτού, έχοντας ως βασικό στόχο την ελαχιστοποίηση του αλγεβρικού του βαθμού. Αρχικά αποσυνθέτουμε το βασικό κατηγόρημα σε υποκατηγορήματα, τα οποία βασίζονται με τη σειρά τους σε πιο βασικούς γεωμετρικοαλγεβρικούς ελέγχους. Αποδεικνύουμε ότι το σύνολο των υποκατηγορημάτων και άρα και το κεντρικό κατηγόρημα απαιτεί υπολογισμούς αλγεβρικού βαθμού το πολύ 10 για να απαντηθεί για μη εκφυλισμένες εισόδους. Επίσης, για του ίδιου τύπου τριχοτόμους, αποδεικνύουμε ότι όλα τα υποκατηγορήματα που έχουμε σχεδιάσει απαιτούν μέγιστο αλγεβρικό βαθμό 10 ή 8, εάν απαιτούν τονενδιάμεσο υπολογισμό του κατηγορήματος InSphere ή όχι.Ανάμεσα στα εργαλεία που χρησιμοποιούμε είναι ο μετασχηματισμός αντιστροφής και η συμβολική διαταραχή. Το μεγαλύτερο μέρος της ανάλυσής μας γίνεται στον αντεστραμμένο χώρο, όπου οι γεωμετρικές μας παρατηρήσεις μεταφράζονται σε αλγεβρικούς όρους.