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 d...
详细信息
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 efficient, 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.
We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in d. We focus on the situation when the input point set is supported by certain basic (and commonly used) geome...
详细信息
We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in d. We focus on the situation when the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within 1 + Ε using only Õ(√n poly(1/Ε)) queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbors queries.
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets who...
详细信息
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O(log Δ) times optimal, Δ being the maximum degree of the input network. This is best-possible if NP DTIME[nO(log log n)] and if the processors are limited to polynomial-time computation. We then show how to construct dominating sets which satisfy the above properties, as well as the "low stretch" property that any two adjacent nodes in the network have their dominators at a distance of at most O(log n) in the network. (Given a dominating set S, a dominator of a vertex u is any v ∈ S such that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal.
暂无评论