Computer Science – Computational Geometry
Scientific paper
2006-02-28
Computer Science
Computational Geometry
Scientific paper
Let $k$ and $n$ be positive integers, $n>k$. Define $r(n,k)$ to be the minimum positive value of $$ |\sqrt{a_1} + ... + \sqrt{a_k} - \sqrt{b_1} - >... -\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(n/\log n)} \log n$, which is better than the best known result $O(2^{2k} \log n)$ whenever $ n \leq ck\log k$ for some constant $c$. In particular, our result implies a {\em subexponential} algorithm to compare two sums of square roots of integers of size $o(k\log k)$.
No associations
LandOfFree
On comparing sums of square roots of small integers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On comparing sums of square roots of small integers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On comparing sums of square roots of small integers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-550044