When a group I_1,... ,I_n of individuals wishes to collaboratively construct a complex multimedia document, the first requirement is that they be able to manipulate media-objects created by one another. For instance, if individual I_j wishes to access some media objects present at participant I_k's site, he must be able to; (1) retrieve this object from across the network, (2) ensure that the object is in a form that is compatible with the viewing/editing resources he has available at his node, and (3) ensure that the object has the desired quality (such as image size and resolution). Furthermore, he must be able to achieve these goals at the lowest possible cost. In this paper, we develop a theory of media objects, and present optimal algorithms for collaborative object sharing/synthesis of the sort envisaged above. We then extend the algorithms to incorporate quality constraints (such as image size) as well as distribution across multiple nodes. The theoretical model is validated by an experimental implementation that supports the theoretical results. (Also cross-referenced as UMIACS-TR-96-8)