E-Locus - Institutional Repository of the University of Crete - Κατηγορήματα Ευκλείδειου διαγράμματος Voronoi ευθύγραμμων τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45 με τους άξονες

Home Κατηγορήματα Ευκλείδειου διαγράμματος Voronoi ευθύγραμμων τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45 με τους άξονες

Results - Details

[Add to Basket]

Identifier

000369014

Title

Κατηγορήματα Ευκλείδειου διαγράμματος Voronoi ευθύγραμμων τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45 με τους άξονες

Alternative Title

Predicates for the Euclidean Voronoi Diagram of Axis-Aligned and Ortho-45 Line Segments

Author

Καμαριανάκης, Εμμανουήλ Νικολάου

Thesis advisor

Καραβέλας, Μενέλαος

Abstract

In this thesis we study the most-demanding predicate for computing the Euclidean Voronoi diagram of axes-aligned and ortho-45° line segments, namely the Incircle predi¬cate. Our primary goal is to minimize its algebraic degree. In our predicate analysis we show that the Incircle predicate for axis-aligned segments can be answered by evaluating the signs of algebraic expressions of degree at most 6; this is half the algebraic degree we get when we evaluate the Incircle predicate using the current state-of-the-art approach. To achieve this, we reformulate the predicate as a problem of comparing two distances (as opposed to squares of distances in previous approaches) and reduce the problem of comparing these distances to the problem of computing the sign of the value of a (linear or quadratic) polynomial (in one variable), when evaluated at a known specific root of a quadratic polynomial (again in one variable). Respectively, we show that the Incircle predicate for axis-aligned and/or ortho-45° segments can be answered by evaluating the signs of algebraic expressions of degree at most 12. This is the best degree one can achieve when there exist segments that are neither parallel nor perpendicular to each other.

Language

Greek

Subject

Ευθύγραμμα τμήματα

Ευκλείδειο διάγραμμα Voronoi

Κατηγόρημα Incircle

Παράλληλα με τους αξόνες

Υπολογιστική Γεωμετρία

Υπό γωνία 45 με τους άξονες

Issue date

2011-09-11

Collection