On the complexity of coordinated display of multimedia objects

✍ Scribed by Martha L. Escobar-Molano; Shahram Ghandeharizadeh

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 387 KB
• Volume: 242
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00217-5

✦ Synopsis

A multimedia presentation can be represented as a collection of objects with temporal constraints that deÿne when the objects are rendered. The display of a presentation is termed coordinated when the display of its objects respects the pre-speciÿed temporal constraints. Otherwise, the display might su er from failures that translate into meaningless scenarios. For example, a chase scene between a dinosaur and a jeep becomes meaningless if the system fails to render the dinosaur when displaying the scene.

A previous study (M.L. Escobar-Molano et al., IEEE Trans. Knowledge Data Eng. 8 (3) (1996) 508 -511) introduced a resource scheduling technique that guarantees a coordinated display of a presentation for single-disk architectures. This technique minimizes both latency and memory requirements and has a worst case time complexity O(n lg n). This paper extends the previous study to multi-disk architectures and demonstrates the following: (1) the computation of a resource schedule that supports a coordinated display and yields the minimum latency is NP-hard, and (2) the computation of the minimum memory requirements to support a coordinated display within a pre-speciÿed latency is NP-hard.