The Complexity of Dance Choreography Procedures
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:
PDFRefbacks
- There are currently no refbacks.