期刊
ACM TRANSACTIONS ON ALGORITHMS
卷 5, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1541885.1541889
关键词
Ray shooting; planar point location
We consider the dynamic vertical ray shooting problem against horizontal disjoint segments, that is, the task of maintaining a dynamic set S of n nonintersecting horizontal line segments in the plane under a query that reports the first segment in S intersecting a vertical ray from a query point. We develop a linear-size structure that supports queries, insertions, and deletion in O(log n) worst-case time. Our structure works in the comparison model on a random access machine.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据