Affordable Access

Publisher Website

Generalized guarding and partitioning for rectilinear polygons

Authors
Journal
Computational Geometry
0925-7721
Publisher
Elsevier
Publication Date
Volume
6
Issue
1
Identifiers
DOI: 10.1016/0925-7721(96)00014-4
Keywords
  • Rectilinear Polygons
  • Polygon Decomposition
  • Visibility
Disciplines
  • Computer Science

Abstract

Abstract A T k -guard G in a rectilinear polygon P is a tree of diameter k completely contained in P. The guard G is said to cover a point x if x is visible from some point contained in G. We investigate the function r( n, h, k), which is the largest number of T k -guards necessary to cover any rectilinear polygon with h holes and n vertices. The aim of this paper is to prove new lower and upper bounds on parts of this function. In particular, we show the following upper bounds: 1. r(n,0,k)⩽ n k+4  , with equality for even k. 2. r(n,h,1)= n+ 4h 3 + 4 3 4+ 4 3  3. (n,h,2)⩾ n 6 These bounds, along with other lower bounds that we establish, suggest that the presence of holes reduces the number of guards required, if k > 1. In the course of proving the upper bounds, new results on partitioning are obtained which also have efficient algorithmic versions.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Minimum K-partitioning of rectilinear polygons

on Journal of Symbolic Computatio... Jan 01, 1990

On guarding the vertices of rectilinear domains

on Computational Geometry Jan 01, 2008

The contour problem for rectilinear polygons

on Information Processing Letters Jan 01, 1984
More articles like this..