Multimedia documents are composed of different data types such as video, audio, text, and images. Authoring a multimedia document is a creative exercise. Unlike traditional computer supported collaborative work where documents are composed of static objects, multimedia documents have temporal and spatial requirements that must be supported by any collaborative multimedia platform. In this paper, we show that most requirements Ž . including temporal and spatial for collaborative multimedia authoring systems can be expressed in terms of a highly structured class of linear constraints called prioritized difference constraints. Based on our prioritized difference constraint-based characterization, we develop efficient, incremental algorithms for creating and modifying multimedia documents so as to satisfy the required temporal and spatial constraints. We further develop methods to identify inconsistent requirements, and show how such inconsistencies may be removed through constraint relaxation techniques. We also report on the Ž . collaborati¨e heterogeneous interacti¨e multimedia platform CHIMP system developed using the framework described.