We are concerned with generating natural language locative phrases with respect to a map in response to "Where is" type queries by a user. We restrict our problem by assuming that the correct ground (reference point) to use for locating a figure (place being located), is a stationary landmark of enough size and importance that is visible on the map. Hence, our problem involves choosing a suitable landmark for the ground, building a knowledge representation to express the relationship of the figure to the ground, and generating natural language to express that relationship. Our work has resulted in an extension to a generation grammar for a multi-modality interface system that selects a reference point and expresses the location of an object with respect to the selected reference point. In doing so, the system attends to what is prominent on the map, and what has been used recently to orient the addressee. The development of our extension has clarified several research issues related to generating natural language consistent with, and appropriate to visual information displayed on map.