The Complexity of Dance Choreography Procedures

Nigel Gwee .


We derive the conceptual link between dance
choreography and other significant problems in computer
science, mathematics, and operations research. Dance
choreography problems, formulated as decision problems,
are shown to be NP-Complete. The corresponding
optimization problems are shown to be NP-Hard and NPEasy,
and hence NP-Equivalent. We discuss the rationale
behind these classifications, and evaluate various
algorithmic solutions and their implementations.

Full Text:



  • There are currently no refbacks.