The assessment of, and planning for, service coverage has been a fundamental aspect of geographic research. In particular, facility placement and associated coverage are central concerns in emergency services, transit route design, cartographic simplification, natural resource management, and weather monitoring, among others. In this article the widely applied set-covering problem is discussed, focusing on its use in geographic analysis. Problematic aspects of set-coverage modeling across space are identified. In particular, geographic information systems (GIS) and enhanced spatial information have accentuated abstraction/spatial representation issues in need of greater consideration in modeling service coverage. To address representational problems with existing approaches, a new set-covering model is introduced for dealing with spatial objects (points, lines, polygons, arcs, curves, etc.). The developed approach accounts for complementary coverage of objects. In doing this, the model decreases modifiable areal unit problem impacts known to be an issue in the geographic application of the set-covering problem. Empirical results are presented to support the usefulness and validity of this new approach.