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
be some set of orientations, that is,
. We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in
. We call such curves
-staircases. Two points p andq in a polygonP are said to
-see each other if an
-staircase fromp toq exists that is completely contained inP. The
-kernel of a polygonP is then the set of all points which
-see all other points. The
-kernel of a simple polygon can be obtained as the intersection of all { }-kernels, with ![theta](/content/m475552471371324/xxlarge952.gif)
. With the help of this observation we are able to develop an
algorithm to compute the
-kernel of a simple polygon, for finite
. We also show how to compute theexternal
-kernel of a polygon in optimal time
. The two algorithms are combined to compute the (
-kernel of a polygon with holes in time
.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 等数据库收录! |
|