線分の交点列挙問題に対する平面走査法の改良

DOI Web Site 参考文献12件

書誌事項

タイトル別名
  • Improvement on the Plane Sweep Method for Finding All Intersections of Line Segments
  • センブン ノ コウテン レッキョ モンダイ ニ タイスル ヘイメン ソウサホウ

この論文をさがす

説明

This paper presents an improvement on the plane sweep algorithm for finding all the intersections of line segments in the plane. Bentley and Ottmann gave an O(N+K)space, O((N+K)longN) time algorithm using the sweep line method where N is the number of line segments and K is the number of intersections. Schorn reduced the arithmetic precision required in the algorithm without increasing the time complexity. However, his algorithm requires additional procedures, which make the algorithm slower. The algorithm proposed in this paper has the same time complexity as the previous ones, but requires less number of computation than Schorn's method and less arithmetic precision than the Bently-Ottmann method. The superiority of the new algorithm is also shown by computational experiments.

収録刊行物

参考文献 (12)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ