2002 · 23 citations · 20 references
Natural SciencesMathematicsTopologyFundamental GroupHomological AlgebraHomotopy TheoryKnot TheoryHomotopy Classes Of Maps
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.
20
Algorithms for Reporting and Counting Geometric Intersections
Bentley, Ottmann · IEEE Transactions on Computers · 1979 · 999 citations
Making data structures persistent
James R. Driscoll, Neil Sarnak, Daniel D. Sleator et al. · 1986 · 704 citations
Lower bounds for algebraic computation trees
Michael Ben-Or · 1983 · 527 citations · Full text