Radio Frequency Identification (RFID) technologies are applied in many fields for a variety of applications today. Recently, new solutions are proposed to deploy RF tags on the ground instead of attaching them to objects for RFID-based monitoring and localization. However, the optimal tag deployment strategy is yet to be addressed. In this paper, we identify the optimal deployment patterns that guarantee k-covering (i.e., at least k RFID tags are accessible anywhere in the deployment region), where k <= 3. In addition, we analyze the achievable minimum upper bound and the average of localization error when the optimal deployment patterns are applied. The numerical results show that our optimal deployment patterns significantly reduce the required number of tags for k-covering compared with the square pattern which is commonly used in RFID-based monitoring and localization systems. The comparison between simulation and analytical results shows that our analytical models provide very accurate estimations of localization error. (C) 2010 Elsevier Ltd. All rights reserved.