首页 | 本学科首页   官方微博 | 高级检索  
     


Staircase visibility and computation of kernels
Authors:S Schuierer  D Wood
Affiliation:(1) Institut für Informatik, Universität Freiburg, Rheinstrasse 10–12, D-79104 Freiburg, Germany;(2) Department of Computer Science, University of Western Ontario, N6A 5B7 London, Ontario, Canada
Abstract:Let 
$$\mathcal{O}$$
be some set of orientations, that is, 
$$\mathcal{O} \subseteq 0^\circ ,360^\circ ]$$
. We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in 
$$\mathcal{O}$$
. We call such curves 
$$\mathcal{O}$$
-staircases. Two points p andq in a polygonP are said to 
$$\mathcal{O}$$
-see each other if an 
$$\mathcal{O}$$
-staircase fromp toq exists that is completely contained inP. The 
$$\mathcal{O}$$
-kernel of a polygonP is then the set of all points which 
$$\mathcal{O}$$
-see all other points. The 
$$\mathcal{O}$$
-kernel of a simple polygon can be obtained as the intersection of all {theta}-kernels, with thetaisin 
$$\mathcal{O}$$
. With the help of this observation we are able to develop an 
$$O(n\log \left| \mathcal{O} \right|)$$
algorithm to compute the 
$$\mathcal{O}$$
-kernel of a simple polygon, for finite 
$$\mathcal{O}$$
. We also show how to compute theexternal 
$$\mathcal{O}$$
-kernel of a polygon in optimal time 
$$O(n + \left| \mathcal{O} \right|)$$
. The two algorithms are combined to compute the ( 
$$\mathcal{O}$$
-kernel of a polygon with holes in time 
$$O(n^2  + n\left| \mathcal{O} \right|)$$
.This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.
Keywords:Restricted orientation geometry  Computational geometry  Polygons  Kernel problem
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号