“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 11137 |
|
||||
| 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 with more cost in the preprocessing phase. Our algorithm is based on solutions in [13] and [2] proposed for simple polygons. In our solution, the preprocessing is done in time O(n3 log(n)) to construct a data structure of size O(n3). It is then possible to report the visibility polygon of any query point q in time O((1+h') log n+ - 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 | |||||
