Partitioning crowded virtual environments

We investigate several techniques that partition a crowded virtual environment into regions that can be managed by separate servers or mapped onto different multicast groups. When constructing a partitioning, we attempt to minimize overhead of the partitioning with respect to network management, whilst maintaining a bound on the number of entities that are mapped to any particular server or group.We compare several partitioning schemes: quad tree, k-d tree unconstrained, k-d tree constrained, and region growing. With our simulations of a crowded virtual environment modelled on a part of central London, we find that the region growing technique give the best overall results.