“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 10840 |
|
||||||
| Abstract: | |||||||
|
Determining whether two segments s and t in a planar polygonal scene weakly see each other is a classical problem in computational geometry. In this problem we seek for a segment connecting two points of s and t without intersecting edges of the scene. In planar polygonal scenes, this problem is 3sum-hard and its time complexity is O(n 2) where n is the complexity of the scene. This problem can be defined in the same manner when s and t are any kind of objects in the plane. In this paper we consider this problem when s and t can be points, segments or convex polygons. We preprocess the scene so that for any given pair of query objects we can solve the problem efficiently. In our presented method, we preprocess the scene in O(n 2?+?e ) time to build data structures of O(n 2) total size by which the queries can be answered in O(n 1?+?e ) time. Our method is based on the extended visibility graph [1] and a range searching data structure presented by Chazelle et al. [2].
Download TeX format |
|||||||
| back to top | |||||||
