Abstract In 1973, Victor Klee posed the following question: How many guards are necessary,
and how many are sufficient to patrol the paintings and works of art in an art gallery with n …

Handbook of DISCRETE AND COMPUTATIONAL GEOMETRY Page 1 i “K25063” — 2017/9/15
— 18:58 — page 875 — i i i 33 VISIBILITY Joseph O’Rourke INTRODUCTION In a …

The placement of sensors to support security monitoring is obviously critical as it will directly
impact the efficacy of allocated resources and system performance. It is critical to be able to …

Past research on art gallery problems has concentrated almost exclusively on bounds on the
numbers of guards needed in the worst case in various settings. On the complexity side …

We present the first constant-factor approximation algorithm for a nontrivial instance of the
optimal guarding (coverage) problem in polygons. In particular, we give an O(1) …

During the last decade, Geographical Information Systems (GISs) have gained a great
impact over a variety of important application fields [171]. According to Goodchild, Kemp …

In plastic injection moulding process, cooling channel design is an essential factor that
affects the quality of the moulded parts and the productivity of the process. Non-uniform …

Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-
regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for …

We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at
vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is …

We present approximation algorithms and heuristics for several variations of terrain
guarding problems, where we need to guard a terrain in its entirety by a minimum number of …