On determining non-isotopic configurations of points on a circle

On determining non-isotopic configurations of points on a circle

0.00 Avg rating0 Votes
Article ID: iaor1997991
Country: Netherlands
Volume: 59
Issue: 1
Start Page Number: 33
End Page Number: 50
Publication Date: Apr 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: optimization
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.