Testing Homotopy for paths in the plane
Sergio Cabello, Yuanxin Liu, Andrea Mantler, Jack Scott Snoeyink · 2002
In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For simple paths specified by n line segments with obstacles described by n points, our algorithm runs in O(n log n) time, which we show is tight. For self-intersecting paths the problem is related to Hopcroft's problem.