An important and challenging task in cartography is the labeling of maps-attaching text to geographic features. Usually, the features to be labeled are regions, lines, and points on a map. One of the traditional formulations of the problem of labeling points is the point-feature-label placement problem, where we are given a set of points in the plane, and an axis-parallel rectangular label associated with each point, and the problem is to place each label with one corner at its associated point such that no two labels overlap. [KIm88, FWa91, MSh91, KRa92] This problem is known to be NP-complete. There are approximation algorithms when the problem consists of scaling the labels.