On determining non-isotopic configurations of points on a circle Original Research Article

Given a set P of 2n colored points on a circle O, a configuration of P is a set B of n non-intersecting chords of O such that each chord passes through two points in P of the same color. Two configurations B1 and B2 of P are isotopic if we can move, enlarge, or shrink the chords in B1 (no two chords may contact each other during the process) so that the resulting configuration is identical to B2. We describe linear time algorithms for determining if P has a configuration and if P has at least two non-isotopic configurations.