A Linear Time Algorithm for the Flip Distance between Plane Spanning Paths in Convex Point Sets

Key Points

• The central aim is to develop a linear time algorithm to compute the flip distance between two plane spanning paths in convex configurations.
• Developed a linear time algorithm for calculating flip distance.
• Examined the happy edge property in the context of convex point sets.
• Adapted the algorithm for compatible flips, local flips, and paths in simple polygons.
• Successfully calculated flip distance in linear time.
• Demonstrated that the happy edge property does not hold for convex point sets.
• The algorithm's adaptability allows for additional types of flips.

Abstract