Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
On Comparing Sums of Square Roots of Small Integers
verfasst von : Qi Cheng
Erschienen in: Mathematical Foundations of Computer Science 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
k
and
n
be positive integers,
n
>
k
. Define
r
(
n
,
k
) to be the minimum positive value of
$ |\sqrt{a_1} + \cdots + \sqrt{a_k} -- \sqrt{b_1} -- \cdots -\sqrt{b_k} | $
where
a
1
,
a
2
, ⋯,
a
k
,
b
1
,
b
2
, ⋯,
b
k
are positive integers no larger than
n
. It is an important problem in computational geometry to determine a good upper bound of –log
r
(
n
,
k
). In this paper we prove an upper bound of 2
$^{O({\it n}/log{\it n})}$
, which is better than the best known result
O
(2
2
k
log
n
) whenever
n
≤
ck
log
k
for some constant
c
. In particular, our result implies an algorithm
subexponential
in
k
(i.e. with time complexity 2
$^{o({\it k})}$
(log
n
)
O
(1)
) to compare two sums of square roots of integers of value
o
(
k
log
k
).