2007 International Conference on Computational Science and its Applications , 2007-08-26

Title : ( Weak Visibility of Two Objects in Planar Polygonal Scenes )

Authors: Mostafa Nouri Baygi , Alireza Zarei , Mohammad Ghodsi ,

Citation: BibTeX | EndNote

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 Ω(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 + ε ) time to build data structures of O(n 2) total size by which the queries can be answered in O(n 1 + ε ) time. Our method is based on the extended visibility graph [1] and a range searching data structure presented by Chazelle et al. [2].

Keywords

, Computational geometry, weak visibility, 3sum-hard problems, object
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1038798,
author = {Nouri Baygi, Mostafa and Alireza Zarei and Mohammad Ghodsi},
title = {Weak Visibility of Two Objects in Planar Polygonal Scenes},
booktitle = {2007 International Conference on Computational Science and its Applications},
year = {2007},
location = {کوالالامپور},
keywords = {Computational geometry; weak visibility; 3sum-hard problems; object inter-visibility},
}

[Download]

%0 Conference Proceedings
%T Weak Visibility of Two Objects in Planar Polygonal Scenes
%A Nouri Baygi, Mostafa
%A Alireza Zarei
%A Mohammad Ghodsi
%J 2007 International Conference on Computational Science and its Applications
%D 2007

[Download]