Résumé: In order to .nd all intersections amongpolygonal chains, this paper presents a procedure consistingof two phases: ( 1) splittingpolygonal chains into a minimal number of monotone chains and ( 2) .ndingintersections amongthe monotone chains. For the .rst phase, we suggest an optimal algorithm splitting polygonal chains into a minimal number of monotone chains, with an O ? n ? + r log r time complexity, where n is the number of line- segments in the polygonal chains and r is the number of C- subchains For the second phase, we extend Bentley –Ottmann ’s sweep- line algorithm and the time complexity is O((? n +? k) log m) ; where k is the number of intersections, and m is the minimal number of monotone chains.

Langue: Anglais