Advertisement
Published in:
2010 | OriginalPaper | Chapter
Online Uniformly Inserting Points on Grid
Authors : Yong Zhang, Zhuo Chang, Francis Y. L. Chin, Hing-Fung Ting, Yung H. Tsin
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we consider the problem of inserting points in a square grid, which has many background applications, including halftone in reprographic and image processing. We consider an online version of this problem, i.e., the points are inserted one at a time. The objective is to distribute the points as uniformly as possible. Precisely speaking, after each insertion, the gap ratio should be as small as possible. In this paper, we give an insertion strategy with a maximal gap ratio no more than
$2\sqrt{2}\approx 2.828$
, which is the first result on uniformly inserting point in a grid. Moreover, we show that no online algorithm can achieve the maximal gap ratio strictly less than 2.5 for a 3×3 grid.