空間分割法を用いた線分交差列挙アルゴリズム

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2016/12/01

タイトル(英語): An Algorithm for Enumerating Intersections of Line Segments Using Space Segmentation Method

著者名: 山本　修身（名城大学理工学部情報工学科），石河　孝太（名城大学大学院理工学研究科情報工学専攻）

著者名(英語): Osami Yamamoto (Faculty of Science and Technology, Department of Information Engineering, Meijo University), Kota Ishikawa (Division of Science and Technology, School of Information Engineering, Meijo University)

キーワード: メッシュ系，メッシュ要素，並列アルゴリズム，マルチコアアーキテクチャ　　mesh system，mesh elements，parallel algorithms，multi-core architecture

要約(英語): This paper describes a space segmentation method (SSM)-based algorithm for enumerating all intersections of given line segments on a bounded plane, which is a classical problem in computational geometry. Here, SSM is an algorithm for finding all combinations of input data that generate points satisfying some conditions for a particular space. Assuming that the minimum distance between these points is bounded, the algorithm finds the combinations by recursively segmenting the space. Defining a hierarchical mesh system, we designed an efficient and simple algorithm for the line segment intersection enumeration problem. Although we have been unable to estimate the computational complexity of the algorithm, the performance on random inputs of a program implementing the algorithm was extremely high. It was also faster than an implementation of a well-known algorithm by Bentley and Ottmann(4). Moreover, as our algorithm is quite simple, it can easily be rewritten as a parallel program. In a twelve-threaded environment, such a program ran approximately 2.6 times faster than a single-threaded version of the program.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.136 No.12 （2016） 特集Ⅰ：電気・電子・情報関係学会東海支部連合大会　特集Ⅱ：国際会議ACIS 2014/2015

本誌掲載ページ: 1683-1690 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/136/12/136_1683/_article/-char/ja/