We consider the problem of determining the rational number which best approximates the real number a and such that its denominator belongs to an interval [b, b']. There is a related geometric problem consisting in...
详细信息
We consider the problem of determining the rational number which best approximates the real number a and such that its denominator belongs to an interval [b, b']. There is a related geometric problem consisting in finding the integer point lying in the vertical domain D of the form {(x, y) is an element of R(2) vertical bar b <= x <= b'} such that the straight line passing through the origin and through this point best approximates the straight line L of slope a passing through the origin. The computation of this point is interlinked with the computation of both the convex hulls of the integer points located above and below the straight line L respectively and lying in the vertical domain D. In the literature, many general convex hull algorithms exist, as the gift wrapping algorithm for example. However, we focus on two interesting approaches to compute these convex hulls which are especially appropriated in our special configuration. The first one mainly uses number theory and runs in 0(log(b')) time. The other is in line with computational geometry as the method proposed in 1999 by Balza-Gomez er al. [H. Balza-Gomez, J.-M. Moreau, D. Michelucci, Convex hull of grid points below a line or a convex curve, in: DGCI '99: Proceedings of the 8th International Conference on Discrete Geometry for Computer Imagery, Springer, Marne-la-Vallee, France, 1999, pp. 361-374] which runs in O(log(b' - b)) time. We propose a new method for the computation of these convex hulls which combines number theory and computational geometry. Our method preserves the optimal timecomplexity and is the first being output sensitive. Indeed, we compute the convex hulls in time linear in their vertex number. Moreover, the resulting algorithm is very simple and so is suitable for implementation. (C) 2009 Elsevier B.V. All rights reserved.
An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the app...
详细信息
An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the application. A weak point in this technique is that the timecomplexity is linear in the number of updates to the value represented by the open ended list. In this programming pearl we present a variant of the open ended list, namely an open ended tree, with an update and access timecomplexitylogarithmic in the number of updates to the value.
Let us consider a two-dimensional linear constraint C of the form ax + by <= c with integer coefficients and such that vertical bar a vertical bar <= vertical bar b vertical bar. A constraint C' of the form ...
详细信息
ISBN:
(纸本)9783540782742
Let us consider a two-dimensional linear constraint C of the form ax + by <= c with integer coefficients and such that vertical bar a vertical bar <= vertical bar b vertical bar. A constraint C' of the form a'x + b'y <= c' is equivalent to C relative to a domain iff all the integer points in the domain satisfying C satisfy C' and all the integer points in the domain not satisfying C do not satisfy C'. This paper introduces a new method to transform a constraint C into an equivalent constraint C' relative to a domain defined by {(x , y) vertical bar h <= x <= h + D} such that the absolute values of a' and b' do not exceed D. Our method achieves a O(log(D)) timecomplexity and it can operate when the constraints coefficients are real values with the same timecomplexity. This transformation can be used to compute the convex hull of the integer points which satisfy a system of n two-dimensional linear constraints in O(n log(D)) time where D represents the size of the solution space. Our algorithm uses elementary statements from number theory and leads to a simple and efficient implementation.
many algorithms proposed to generate Fibonacci series introduced by a 12th century Italian mathematician Leonardo Bonacci [1]. The study paper gives insight into three different Fibonacci series generation algorithms....
详细信息
ISBN:
(纸本)9781467392068
many algorithms proposed to generate Fibonacci series introduced by a 12th century Italian mathematician Leonardo Bonacci [1]. The study paper gives insight into three different Fibonacci series generation algorithms. This paper compares and contrasts three different algorithms namely LINEAR_FIB, EXPO_FIB and MATRIX_FIB. time complexities of these algorithms are computed. The results of our study show that the three algorithms gives linear, exponential and logarithmictime complexities. Finally we discussed application areas of Fibonacci numbers which are generated by the algorithms.
One of the most important characteristics of all error control codes (ECCs) is the complexity of the encoding/decoding algorithms. Today, there are many ECCs that can correct multiple bit errors, but at the price of h...
详细信息
One of the most important characteristics of all error control codes (ECCs) is the complexity of the encoding/decoding algorithms. Today, there are many ECCs that can correct multiple bit errors, but at the price of high encoding/decoding complexity. Among the rare exceptions are integer ECCs (IECCs), whose serial encoding/decoding algorithms run in O(n) time, where n is the codeword length. In this article, we show that IECCs can be encoded/decoded even faster, that is, that their parallel encoding/decoding algorithms have O(log(2) n) timecomplexity.
暂无评论