| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429239 | Information Processing Letters | 2006 | 8 Pages |
Abstract
Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
