| This thesis contains a collection of results in computational geometry that are inspired from music theory literature. The solutions to the problems discussed are based on a representation of musical rhythms where pulses are viewed as points equally spaced around the circumference of a circle and onsets are a subset of the pulses. All our results for rhythms apply equally well to scales, and many of the problems we explore are interesting in their own right as distance geometry problems on the circle.;In this thesis, we characterize two families of rhythms called deep and Euclidean. We describe three algorithms that generate the unique Euclidean rhythm for a given number of onsets and pulses, and show that Euclidean rhythms are formed of repeating patterns of a Euclidean rhythm with fewer onsets, followed possibly by a different rhythmic pattern. We then study the conditions under which we can transform one Euclidean rhythm to another through five different operations. In the context of measuring rhythmic similarity, we discuss the necklace alignment problem where the goal is to find rotations of two rhythms and a perfect matching between the onsets that minimizes some norm of the circular distance between the matched points. We provide o (n2)-time algorithms to this problem using each of the ℓ1, ℓ2, and ℓinfinity norms as distance measures. Finally, we give a polynomial-time solution to the labeled beltway problem where we are given the ordering of a set of points around the circumference of a circle and a labeling of all distances defined by pairs of points, and we want to construct a rhythm such that two distances with a common onset as endpoint have the same length if and only if they have the same label. |
