Collective animal behavior studies have led the way in developing models that account for a large number of individuals, but have mostly considered situations where alignment and attraction play a key role, such as in schooling and flocking. By quantifying how animals react to each others' presence, when interaction is via conspecific avoidance rather than alignment or attraction, we present a mechanistic insight that enables us to link individual behavior and space use patterns. As animals respond to both current and past positions of their neighbors, the assumption that the relative location of individuals is statistically and history-independent is not tenable, underscoring the limitations of traditional space use studies. We move beyond that assumption, by constructing a framework to analyze spatial segregation of mobile animals when neighbor proximity may elicit a retreat, and by linking conspecific encounter rate to history-dependent avoidance behavior. Our approach rests on the knowledge that animals communicate by modifying the environment in which they live, providing a method to analyse social cohesion as stigmergy, a form of mediated animal-animal interaction. By considering a population of animals that mark the terrain as they move, we predict how the spatio-temporal patterns that emerge depend on the degree of stigmergy of the interaction processes. We find in particular that non-local decision rules may generate a nonmonotonic dependence of the animal encounter rate as a function of the tendency to retreat from locations recently visited by other conspecifics, which has fundamental implications to epidemic disease spread and animal sociality.