“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 10831 |
|
||||
| Abstract: | |||||
|
In this paper, we consider the problem of computing the visibility of a query point inside polygons with holes. The goal is to perform this computation efficiently per query considering the cost of the preprocessing phase. Our algorithm is based on solutions in [A.L.P. Bose, J.I. Munro, Efficient visibility queries in simple polygons, Computational Geometry: Theory and Applications 23 (3) (2002) 313-335] and [M.T.B. Aronov, L. Guibas, L. Zhang, Visibility queries and maintenance in simple polygons, Discrete and Computational Geometry 27 (4) (2002) 461-483] proposed for simple polygons. In our solution, the preprocessing is done in time O(n^3logn) to construct a data structure of size O(n^3). It is then possible to report the visibility polygon of any query point q in time O((1+h^)logn+ - V(q) - ), in which n and h are the number of the vertices and holes of the polygon respectively, - V(q) - is the size of the visibility polygon of q, and h^ is an output and preprocessing sensitive parameter of at most min(h, - V(q) - ). This is claimed to be the best query-time result on this problem so far.
Download TeX format |
|||||
| back to top | |||||
