Camera placement in integer lattices (extended abstract)
Michel Pocchiola, Evangelos Kranakis · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1990
Abstract: "We consider new techniques for studying an art gallery problem (the camera placement problem) in the infinite lattice L[superscript d] of d tuples of integers. A lattice point A is visible from a camera C (positioned at a vertex of L[superscript 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 we can determine in polynomial time, for any given number s [<or =] 5[superscript d] of cameras, the position they must occupy in the lattice L[superscript d] in order to maximize their visibility. This improves previous results for s [