The Complexity of Dance Choreography Procedures

Nigel Gwee .

Abstract


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:

PDF

Refbacks

  • There are currently no refbacks.