Lower Bound for Sculpture Garden Problem.pdf

The purpose of the current study is to investigate a special case of art gallery problem,namely a sculpture garden problem. In this problem, for a given polygon P, the ultimate goal isto place the minimum number of guards (landmarks) to define the interior polygon P by applyinga monotone Boolean formula composed of the guards. Using this problem, it can replace theoperation-based method with time-consuming, pixel-based algorithms. So, the processing time ofsome problems in the fields of machine vision, image processing and gamification can be stronglyreduced. The problem has also many applications in mobile device localization in the Internet ofThings (IoT). An open problem in this regard is the proof of Eppstein’s conjecture, which has remainedan open problem since 2007. According to his conjecture, in the worst case, n 􀀀 2 vertex guards arerequired to describe any n-gon. In this paper, a lower bound is introduced for the special case of thisproblem (natural vertex guard), which shows that if a polygon can be defined with natural vertexguards, then n - 2 is a lower bound.