Frontier sets in large terrains

In current online games, player positions are synchronized by means of continual broadcasts through the server. This solution is expensive, forcing any server to limit its number of clients. With a hybrid networking architecture, player synchronization can be distributed to the clients, bypassing the server bottleneck and decreasing latency as a result. Synchronization in a decentralized fashion is difficult as each player must communicate with every other player. The communication requirements can be reduced by computing and exploiting frontier sets: For a pair of players in an online game, their frontier sets consist of the region of the game space in which each player may move without seeing (and without communicating to) the other player. This paper describes the first fast and space-efficient method of computing frontier sets in large terrains.