Online uniformity of integer points on a line |
| |
Authors: | Tetsuo Asano |
| |
Affiliation: | School of Information Science, JAIST, 1-1 Asahidai, Nomi, 923-1292 Japan |
| |
Abstract: | This Letter presents algorithms for computing a uniform sequence of n integer points in a given interval [0,m] where m and n are integers such that m>n>0. The uniformity of a point set is measured by the ratio of the minimum gap over the maximum gap. We prove that we can insert n integral points one by one into the interval [0,m] while keeping the uniformity of the point set at least 1/2. If we require uniformity strictly greater than 1/2, such a sequence does not always exist, but we can prove a tight upper bound on the length of the sequence for given values of n and m. |
| |
Keywords: | Algorithms Uniformity Discrepancy Computational geometry |
本文献已被 ScienceDirect 等数据库收录! |
|