Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642020261_13
 Scopus: eid_2s2.070350640924
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Variablesize rectangle covering
Title  Variablesize rectangle covering 

Authors  
Keywords  Base line Directional antenna Polynomialtime algorithms Running time Twodimensional planes 
Issue Date  2009 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09), Yellow Mountains, China, 1012 June 2009. In Lecture Notes in Computer Science, 2009, v. 5573, p. 145154 How to Cite? 
Abstract  In wireless communication networks, optimal use of the directional antenna is very important. The directional antenna coverage (DAC) problem is to cover all clients with the smallest number of directional antennas. In this paper, we consider the variablesize rectangle covering (VSRC) problem, which is a transformation of the DAC problem. There are n points above the base line y=0 of the twodimensional plane. The target is to cover all these points by minimum number of rectangles, such that the dimension of each rectangle is not fixed but the area is at most 1, and the bottom edge of each rectangle is on the base line y=0. In some applications, the number of rectangles covering any position in the twodimensional plane is bounded, so we also consider the variation when each position in the plane is covered by no more than two rectangles. We give two polynomial time algorithms for finding the optimal covering. Further, we propose two 2approximation algorithms that use less running time (O(nlogn) and O(n)). © 2009 Springer Berlin Heidelberg. 
Description  LNCS v. 5573 is conference proceedings of the 3rd International Conference, COCOA 2009 
Persistent Identifier  http://hdl.handle.net/10722/61165 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chin, FYL  en_HK 
dc.contributor.author  Ting, HF  en_HK 
dc.contributor.author  Zhang, Y  en_HK 
dc.date.accessioned  20100713T03:32:19Z   
dc.date.available  20100713T03:32:19Z   
dc.date.issued  2009  en_HK 
dc.identifier.citation  The 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09), Yellow Mountains, China, 1012 June 2009. In Lecture Notes in Computer Science, 2009, v. 5573, p. 145154  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/61165   
dc.description  LNCS v. 5573 is conference proceedings of the 3rd International Conference, COCOA 2009   
dc.description.abstract  In wireless communication networks, optimal use of the directional antenna is very important. The directional antenna coverage (DAC) problem is to cover all clients with the smallest number of directional antennas. In this paper, we consider the variablesize rectangle covering (VSRC) problem, which is a transformation of the DAC problem. There are n points above the base line y=0 of the twodimensional plane. The target is to cover all these points by minimum number of rectangles, such that the dimension of each rectangle is not fixed but the area is at most 1, and the bottom edge of each rectangle is on the base line y=0. In some applications, the number of rectangles covering any position in the twodimensional plane is bounded, so we also consider the variation when each position in the plane is covered by no more than two rectangles. We give two polynomial time algorithms for finding the optimal covering. Further, we propose two 2approximation algorithms that use less running time (O(nlogn) and O(n)). © 2009 Springer Berlin Heidelberg.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.rights  Creative Commons: Attribution 3.0 Hong Kong License   
dc.subject  Base line   
dc.subject  Directional antenna   
dc.subject  Polynomialtime algorithms   
dc.subject  Running time   
dc.subject  Twodimensional planes   
dc.title  Variablesize rectangle covering  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=03029743&volume=5573&spage=145&epage=154&date=2009&atitle=Variablesize+rectangle+covering   
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_HK 
dc.identifier.email  Ting, HF:hfting@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.identifier.authority  Ting, HF=rp00177  en_HK 
dc.description.nature  postprint   
dc.identifier.doi  10.1007/9783642020261_13  en_HK 
dc.identifier.scopus  eid_2s2.070350640924  en_HK 
dc.identifier.hkuros  162177  en_HK 
dc.identifier.hkuros  166446   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.070350640924&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  5573  en_HK 
dc.identifier.spage  145  en_HK 
dc.identifier.epage  154  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Ting, HF=7005654198  en_HK 
dc.identifier.scopusauthorid  Zhang, Y=7601329213  en_HK 