| Optimal dynamic vertical ray shooting in rectilinear planar subdivisions (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. In this paper we consider the dynamic vertical ray shooting problem, that is the task of maintaining a dynamic set S of n non intersecting horizontal line segments in the plane subject to 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 deletions in O(log n) worst-case time. Our structure works in the comparison model and uses a RAM. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||