Online Uniformly Inserting Points on Grid
作者： Yong Zhang , Zhuo Chang , Francis Y. L. Chin , Hing-Fung Ting , Yung H. Tsin
DOI: 10.1007/978-3-642-14355-7_29
关键词:
摘要: In this paper, we consider the problem of inserting points in a square grid, which has many background applications, including halftone reprographic and image processing. We an online version problem, i.e., are inserted one at time. The objective is to distribute as uniformly possible. Precisely speaking, after each insertion, gap ratio should be small give insertion strategy with maximal no more than 2√2 ≈ 2.828, first result on point grid. Moreover, show that algorithm can achieve strictly less 2.5 for 3 ×
springer.com
core.ac.uk
harvard.edu
hku.hk
sci-hub.st 参考文章(5)
Bernard Chazelle, The Discrepancy Method: Randomness and Complexity ,(2000)
Charles R. Collins, Kenneth Stephenson, A circle packing algorithm Computational Geometry: Theory and Applications. ,vol. 25, pp. 233- 256 ,(2003) , 10.1016/S0925-7721(02)00099-8
Sachio Teramoto, Tetsuo Asano, Naoki Katoh, Benjamin Doerr, Inserting Points Uniformly at Every Instance The IEICE transactions on information and systems. ,vol. 89, pp. 2348- 2356 ,(2006) , 10.1093/IETISY/E89-D.8.2348
K. J. Nurmela, P. R. J. Ostergå rd, More optimal packings of equal circles in a square Discrete and Computational Geometry. ,vol. 22, pp. 439- 457 ,(1999) , 10.1007/PL00009472
Tetsuo Asano, Online uniformity of integer points on a line Information Processing Letters. ,vol. 109, pp. 57- 60 ,(2008) , 10.1016/J.IPL.2008.09.008