Name
Title | ||
|---|---|---|
Root comparison techniques applied to computing the additively weighted Voronoi diagram |
Abstract | ||
|---|---|---|
This work examines algebraic techniques for comparing quadratic algebraic numbers, thus yielding methods for deciding key predicates in various geometric constructions. Our motivation and main application concerns a dynamic algorithm for computing the additively weighted Voronoi diagram in the plane. We propose effficient, exact, and complete methods, which are crucial for a fast and robust implementation of these predicates and the overall algorithm. Our first contribution is to minimize, on the one hand, the algebraic degree of the computed quantities, thus optimizing precision and, on the other hand, the total number of arithmetic operations. We focus on the hardest predicate, which involves quadratic polynomials, and detail the corresponding algorithms, which are based on polynomial Sturm sequences; ancillary tools include geometric invariants, multivariate resultants, and polynomial factorization. Our last contribution is a general and efficient implementation, which has been extensively tested in order to demonstrate the practical performance of our methods and the improvements achieved over existing approaches. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.5555/644108.644161 | SODA |
Keywords | Field | DocType |
algebraic degree,polynomial sturm sequence,algebraic technique,quadratic algebraic number,dynamic algorithm,root comparison technique,efficient implementation,overall algorithm,geometric invariants,last contribution,additively weighted voronoi diagram,corresponding algorithm,voronoi diagram,symbolic computation,voronoi diagrams,computational geometry,quadratic algebra,polynomial factorization | Discrete mathematics,Combinatorics,Algebraic number,Polynomial,Discriminant,Computer science,Algorithm,Quadratic equation,Algebraic function,Weighted Voronoi diagram,Voronoi diagram,Factorization of polynomials | Conference |
ISBN | Citations | PageRank |
0-89871-538-5 | 7 | 0.78 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Menelaos I. Karavelas | 1 | 229 | 18.99 |
| Ioannis Z. Emiris | 2 | 949 | 100.40 |