A pseudo-polynomial time O(log² n)-approximation algorithm for art gallery problems

In this thesis, we give a pseudo-polynomial time O(log² n)-approximation algorithm for a variant of the art gallery problem the point-guard problem. The point-guard problem involves finding the minimum number of points and their positions so that guards located at these points cover the interior of the art gallery. Our algorithm is pseudo-polynomial in the sense that it is polynomial in the number of walls of the art gallery but is possibly exponential in the number of bits required to represent the positions of the vertices of the art gallery. Our approach involves reducing the point-guard problem to a new problem of choosing a minimum number of guard-locations from a finite set obtained by a special subdivision procedure. The new problem has the optimal solution at most three times the optional solution of the point-guard problem. We further reduce the new problem to the set cover problem and obtain an approximate solution to the set cover problem.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mechanical Engineering.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Deshpande, Ajay A

Advisor dc:contributor.advisor

• Sanjay E. Sarma.

• Mechanical Engineering.
• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/36243

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/36243