File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online uniformly inserting points on grid

TitleOnline uniformly inserting points on grid
Authors
KeywordsGap ratio
On-line algorithms
Square grid
Image processing
Algorithms
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010), Weihai, China, 19-21 June 2010. In Lecture Notes in Computer Science, 2010, v. 6124, p. 281–292 How to Cite?
AbstractIn 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 √2 ≈ 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. © Springer-Verlag Berlin Heidelberg 2010.
DescriptionLNCS v. 6124 is conference proceedings of 6th international conference, AAIM 2010
Persistent Identifierhttp://hdl.handle.net/10722/125680
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorChang, Zen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorTsin, YHen_HK
dc.date.accessioned2010-10-31T11:45:40Z-
dc.date.available2010-10-31T11:45:40Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010), Weihai, China, 19-21 June 2010. In Lecture Notes in Computer Science, 2010, v. 6124, p. 281–292en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/125680-
dc.descriptionLNCS v. 6124 is conference proceedings of 6th international conference, AAIM 2010-
dc.description.abstractIn 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 √2 ≈ 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. © Springer-Verlag Berlin Heidelberg 2010.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectGap ratio-
dc.subjectOn-line algorithms-
dc.subjectSquare grid-
dc.subjectImage processing-
dc.subjectAlgorithms-
dc.titleOnline uniformly inserting points on griden_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-14355-7_29en_HK
dc.identifier.scopuseid_2-s2.0-79956291392en_HK
dc.identifier.hkuros182342en_HK
dc.identifier.hkuros178826-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79956291392&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6124en_HK
dc.identifier.spage281en_HK
dc.identifier.epage292en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010), Weihai, China, 19-21 June 2010. In Lecture Notes in Computer Science, 2010, v. 6124, p. 281–292-
dc.identifier.scopusauthoridZhang, Y=35114314500en_HK
dc.identifier.scopusauthoridChang, Z=7202170278en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridTsin, YH=6603741679en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats