Camera Placement in Integer Lattices (Extended Abstract)

摘要

Techniques for studying an art gallery problem (the camera placement problem) inthe infinite lattice (L sup d) of d tuples of integers are considered. A lattice point A is visible from a camera C positioned at a vertex of (L sup d) if A does not equal C and if the line segment joining A and C crosses no other lattice vertex. By using a combination of probabilistic, combinatorial optimization and algorithmic techniques the position they must occupy in the lattice (L sup d) in the order to maximize their visibility can be determined in polynomial time, for any given number s less than or equal to (5 sup d) of cameras. This improves previous results for s less than or equal to (3 sup d).