Towards a Multimedia Implementation of an NPComplete Dance Choreography Problem

Abstract

The Dance Choreography problem is NPComplete.
To solve non-trivial instances of such problems,
heuristic algorithms are required, which we have
implemented in our software we call Terpsichore©. The
software creates amalgamations using figures from
established International Standard Ballroom Dance
syllabi, as well as our own proprietary syllabus. A
multimedia-based interface provides various coaching and
teaching modules, delivered in a natural, human-like
manner.