File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Uniformly inserting points on square grid

TitleUniformly inserting points on square grid
Authors
Zhang, YChang, ZChin, FYLTing, HFTsin, YH
KeywordsAlgorithms
Computational geometry
Grid
Point insertion
Uniformity
Issue Date2011
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 2011, v. 111 n. 16, p. 773-779 How to Cite?
DOI: http://dx.doi.org/10.1016/j.ipl.2011.05.001
AbstractWe consider the problem of inserting points in a square grid, which has many motivations, including halftoning in reprography and image processing. The points are inserted one at a time. The objective is to distribute the points as uniformly as possible. More specifically, after each insertion, the gap ratio should be as small as possible. We give an insertion strategy with a maximal gap ratio no more than 22≈2.828, which is the first result in uniformly inserting points 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. © 2011 Elsevier B.V.
Persistent Identifierhttp://hdl.handle.net/10722/139798
ISSN
0020-0190
2021 Impact Factor: 0.851
2020 SCImago Journal Rankings: 0.415
ISI Accession Number ID
WOS:000292795800001
Funding AgencyGrant Number
Shanghai Key Laboratory of Intelligent Information Processing, ChinaIIPL-2010-010
HK RGCHKU 7117/09E
HKU-7171/08E
Funding Information:

Research supported by Shanghai Key Laboratory of Intelligent Information Processing, China. Grant No. IIPL-2010-010.

References
References in Scopus

 

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.accessioned2011-09-23T05:56:07Z-
dc.date.available2011-09-23T05:56:07Z-
dc.date.issued2011en_HK
dc.identifier.citationInformation Processing Letters, 2011, v. 111 n. 16, p. 773-779en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/139798-
dc.description.abstractWe consider the problem of inserting points in a square grid, which has many motivations, including halftoning in reprography and image processing. The points are inserted one at a time. The objective is to distribute the points as uniformly as possible. More specifically, after each insertion, the gap ratio should be as small as possible. We give an insertion strategy with a maximal gap ratio no more than 22≈2.828, which is the first result in uniformly inserting points 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. © 2011 Elsevier B.V.en_HK
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.subjectAlgorithmsen_HK
dc.subjectComputational geometryen_HK
dc.subjectGriden_HK
dc.subjectPoint insertionen_HK
dc.subjectUniformityen_HK
dc.titleUniformly inserting points on square griden_HK
dc.typeArticleen_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.1016/j.ipl.2011.05.001en_HK
dc.identifier.scopuseid_2-s2.0-79957535859en_HK
dc.identifier.hkuros194299en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79957535859&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume111en_HK
dc.identifier.issue16en_HK
dc.identifier.spage773en_HK
dc.identifier.epage779en_HK
dc.identifier.isiWOS:000292795800001-
dc.publisher.placeNetherlandsen_HK
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.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats