Candan, K.S.Prabhakaran, B.Subrahmanian, V.S.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, spatial and quality of service (QoS) requirements that must be supported by any collaborative multimedia platform. In this paper, we show that most requirements (including temporal, spatial, and QoS requirements) for collaborative multimedia systems can be expressed in terms of a highly-structured class of linear constraints called difference constraints that have been well-studied in the operations research literature. As a consequence, well known algorithms for solving difference constraints may be used as a starting point for creating multimedia documents. Based on our difference-constraint based characterization, we develop efficient, incremental algorithms for creating and modifying multimedia documents so as to satisfy the required temporal, spatial and QoS constraints. We further develop methods to identify inconsistent requirements, and show how such inconsistencies may be removed through constraint relaxation techniques. (Also cross-referenced as UMIACS-TR-96-9)en-USTechnical Report