On comparing sums of square roots of small integers
| dc.creator | Cheng, Qi | |
| dc.date | 2006-02-28 | |
| dc.date.accessioned | 2026-07-07T07:05:46Z | |
| dc.date.available | 2026-07-07T07:05:46Z | |
| dc.description | 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)$. | |
| dc.identifier | https://arxiv.org/abs/cs/0603002 | |
| dc.identifier | http://arxiv.org/abs/cs/0603002 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/109781 | |
| dc.subject | Computational Geometry | |
| dc.subject | F.2.1 | |
| dc.title | On comparing sums of square roots of small integers | |
| dc.type | text |