TY - GEN
T1 - A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency
AU - Edahiro, Masato
AU - Tanaka, Katsuhiko
AU - Hoshino, Takashi
AU - Asano, Takao
PY - 1987/10/1
Y1 - 1987/10/1
N2 - The orthogonal segment intersection search problem is stated as follows: Given a set S of n orthogonal segments in the plane, report all the segments of S that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, in O(n) time preprocessing, a search structure of size O(n) so that all the segments of S intersecting a query segment can be reported in O(k) time in the average case, where k is the number of the reported segments. The proposed algorithm as well as existing algorithms its implemented in FORTRAN, and their practical officiencies are investigated through computational experiments. It is shown that our O(k) search time, O(n) space and O(n) preprocessing time algorithm is practically the most efficient among the tested algorithms.
AB - The orthogonal segment intersection search problem is stated as follows: Given a set S of n orthogonal segments in the plane, report all the segments of S that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, in O(n) time preprocessing, a search structure of size O(n) so that all the segments of S intersecting a query segment can be reported in O(k) time in the average case, where k is the number of the reported segments. The proposed algorithm as well as existing algorithms its implemented in FORTRAN, and their practical officiencies are investigated through computational experiments. It is shown that our O(k) search time, O(n) space and O(n) preprocessing time algorithm is practically the most efficient among the tested algorithms.
UR - http://www.scopus.com/inward/record.url?scp=84941506630&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84941506630&partnerID=8YFLogxK
U2 - 10.1145/41958.41986
DO - 10.1145/41958.41986
M3 - Conference contribution
AN - SCOPUS:84941506630
T3 - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
SP - 258
EP - 267
BT - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
A2 - Soule, D.
PB - Association for Computing Machinery, Inc
T2 - 3rd Annual Symposium on Computational Geometry, SCG 1987
Y2 - 8 June 1987 through 10 June 1987
ER -